Problem Statement

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

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

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

整数$N$と$A_1,...,A_N$が与えられるので、このようなグラフの個数を$10^9+7$で割った余りを求めてください。

Input

入力は以下の形式で標準入力から与えられる。

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)$が空白区切りで与えられる。

Output

条件を満たすグラフの個数を$10^9+7$で割った余りを出力せよ。

出力の末尾に改行を入れること。(21:40修正)