AT_arc044_b [ARC044B] 最短路問題

[problemUrl]: https://atcoder.jp/contests/arc044/tasks/arc044_b 高橋君は最短路アルゴリズムが大好きです。毎日さまざまな最短路アルゴリズムを実装して遊んでいます。 しかし、高橋君は最短路を求めすぎてしまったので、最短路を求めるのに飽きてしまいました。 そこで高橋君は、ある頂点からほかの頂点への最短距離が特定の値になるような頂点数が$ N $ですべての辺の長さが1の無向単純グラフの数を数えることにしました。 より正確には、高橋君は同じ頂点の間を結ぶ辺が複数存在せず、またすべての辺の$ 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修正)

### Sample Explanation 1 下図の$ 6 $通りのグラフが条件を満たします。 !\[\](https://arc044.contest.atcoder.jp/img/arc/044/hogehoge/setsumei.png) ### Sample Explanation 2 すべての辺の長さは$ 1 $なので、頂点$ 1,4 $間の距離が$ 0 $となるグラフはありません。 ### Sample Explanation 3 頂点$ 1 $から頂点$ 1 $までの距離は$ 1 $にはなりえません。