No.243 出席番号(2)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 64 MB / 通常問題
タグ : / 解いたユーザー数 25
作問者 : kroton 💸kroton 💸

4 ProblemId : 643 / 出題時の順位表

問題文

$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\) で出力せよ。

サンプル

サンプル1
入力
3
0
1
2
出力
2

1 2 02 0 1の2通りの割り振り方があります。

サンプル2
入力
4
3
3
3
3
出力
0
サンプル3
入力
5
1
1
1
0
1
出力
24
提出ページヘ