問題文

$N$人の生徒がいるクラスがあります。生徒は$S_0$君から$S_{N-1}$君までいます。
それぞれの生徒に$0$から$N-1$までの出席番号を割り振りたいです。
しかし、それぞれの生徒には嫌いな数が1つあり出席番号にしたくありません。
どの生徒にも嫌いな数が当たらないような出席番号の割り振り方は何通りあるか \({\rm mod}\ 10^{9}+7\) で答えよ。

入力

$N$
$A_0$
$A_1$
$\vdots$
$A_{N-1}$

生徒の数$N$が最初の行で与えられる。$1 \le N \le 5000$。
以降の行で$S_i$君の嫌いな数$A_i$が$N$行で与えられる。$0 \le A_i \le 4999$。

出力

どの生徒にも嫌いな数が当たらないような出席番号の割り振り方は何通りあるか \({\rm mod}\ 10^{9}+7\) で出力せよ。

サンプル

3
0
1
2

2

4
3
3
3
3

0

5
1
1
1
0
1

24