← 返回题目列表

AtCoder · arc044_b

B. 最短路径问题

中文机器翻译题面 查看原题

問題文

高桥喜欢最短路径算法。我每天都会实现并尝试各种最短路径算法。 然而,高桥太过于寻找最短路线,所以他厌倦了寻找最短路线。

因此,高桥先生决定找出使一个顶点到另一个顶点的最短距离达到某个值的顶点数。N我决定计算所有边的长度为 1 的无向简单图的数量。

更准确地说,Takahashi 没有连接相同顶点的多条边,并且2具有不同端点顶点的图的顶点依次1,2,...,N作为 任何 对于i,顶点1和顶点 连接i的路径上存在的最小边数为 计算满足A_i的图表总数。 给出了

整数N和A_1,...,A_N,因此我们可以计算出此类图的数量。 除以10^9+7求余数。


入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 ... A_N
  • 1 行显示图中的顶点数。N(1 ≦ N ≦ 10^5)。
  • 2 行包含顶点 来自1的顶点 表示到i的最短距离的整数序列A_1,...,A_N(0 ≦ A_1,...,A_N ≦ N-1)用空格分隔。

出力

满足条件的图数为 打印除以10^9+7后的余数。

在输出末尾插入换行符。 (21:40 修正)

入力例1

4
0 1 1 2

出力例1

6

下图中6下图满足条件。


入力例2

4
0 1 2 0

出力例2

0

所有边的长度是1因此,顶点1,4之间的距离 没有带有0的图表。 到


入力例3

3
1 1 2

出力例3

0

頂点1的顶点 表示到1的距离是 它不能是1。


入力例4

17
0 1 1 2 2 4 3 2 4 5 3 3 2 1 5 4 2

出力例4

855391686