配点 : $900$ 点

問題文

あなたはカエル型のロボットを開発しています。 あなたはこのロボットに競走をさせることにしました。

まず、あなたは数直線上に $N$ 体のロボットを置きました。 ロボットには $1$ から $N$ までの番号が振られています。 今、$i$ 番目のロボットは座標 $x_i$ にいます。 ただし、$x_i$ はすべて整数であり、$0 < x_1 < x_2 < ... < x_N$ が成り立ちます。

あなたは次の操作を繰り返し行います。

• 数直線上のロボットを一体選ぶ。 選んだロボットの座標を $x$ とする。 座標 $x - 1$, $x - 2$ のうち他のロボットがいない座標を着地点に選ぶ。 選んだロボットを着地点へジャンプさせる。

あるロボットの座標が 0 以下になった場合、そのロボットはゴールしたと見なされ、即座に数直線から取り除かれます。 すべてのロボットがゴールするまで、あなたは操作を行い続けます。

あなたが操作を行う方法によって、$N$ 体のロボットがゴールする順番は何通りかありえます。 $N$ 体のロボットがゴールする順番は何通りありうるでしょうか？ $10^9+7$ で割った余りを求めてください。

制約

• $2 \leq N \leq 10^5$
• $x_i$ は整数である。
• $0 < x_1 < x_2 < ... < x_N \leq 10^9$

部分点

• $500$ 点分のテストケースでは、$N \leq 8$ が成り立つ。

入力

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

$N$

$x_1$ $x_2$ $...$ $x_N$

出力

$N$ 体のロボットがゴールする順番は何通りありうるか？ $10^9+7$ で割った余りを出力せよ。

3
1 2 3

4

$3$ 体のロボットがゴールする順番は、次の $4$ 通りありえます。

• $(ロボット 1 \to ロボット 2 \to ロボット 3)$
• $(ロボット 1 \to ロボット 3 \to ロボット 2)$
• $(ロボット 2 \to ロボット 1 \to ロボット 3)$
• $(ロボット 2 \to ロボット 3 \to ロボット 1)$

3
2 3 4

6

$3$ 体のロボットがゴールする順番は、次の $6$ 通りありえます。

• $(ロボット 1 \to ロボット 2 \to ロボット 3)$
• $(ロボット 1 \to ロボット 3 \to ロボット 2)$
• $(ロボット 2 \to ロボット 1 \to ロボット 3)$
• $(ロボット 2 \to ロボット 3 \to ロボット 1)$
• $(ロボット 3 \to ロボット 1 \to ロボット 2)$
• $(ロボット 3 \to ロボット 2 \to ロボット 1)$

例えば、次図のように操作を行うと、$(ロボット 3 \to ロボット 2 \to ロボット 1)$ の順にゴールします。

8
1 2 3 5 7 11 13 17

10080

13
4 6 8 9 10 12 14 15 16 18 20 21 22

311014372

答えを $10^9+7$ で割った余りを出力してください。 なお、このケースは部分点のテストケースには含まれません。