問題文

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

そこで高橋君は、ある頂点からほかの頂点への最短距離が特定の値になるような頂点数が$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修正)

---

入力例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

---