AtCoder Regular Contest 044

B - 最短路問題


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

高橋君は最短路アルゴリズムが大好きです。毎日さまざまな最短路アルゴリズムを実装して遊んでいます。 しかし、高橋君は最短路を求めすぎてしまったので、最短路を求めるのに飽きてしまいました。

そこで高橋君は、ある頂点からほかの頂点への最短距離が特定の値になるような頂点数がNですべての辺の長さが1の無向単純グラフの数を数えることにしました。

より正確には、高橋君は同じ頂点の間を結ぶ辺が複数存在せず、またすべての辺の2端点の頂点が異なるグラフの頂点を順に1,2,...,Nとして、 任意のiに対し、頂点1と頂点iを結ぶ経路上に存在する辺の個数の最小値がA_iになるようなグラフの総数を数えます。

整数NA_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

Submit提出する