F - Share the Recipe
解説
/
実行時間制限: 8 sec / メモリ制限: 1024 MB
配点 : 1300 点
問題文
1 から N までの番号のついた N 台のサーバーがあります. すぬけくんは,秘伝のレシピをサーバー 1 に保存しました. 他のサーバーにはレシピは保存されていません.
これから N(N-1)/2 回,すぬけくんは以下の操作を行います.
- 相異なる 2 つのサーバーを選ぶ. ただし,選ぶサーバーの組は,今まで選んだことのない組でなければならない. なお,組 (x,y) は組 (y,x) と同一とみなす. 操作前の段階で少なくとも一方のサーバーがレシピを保存している場合,操作後には両方のサーバーにレシピが保存される.
操作を行う方法は,(N(N-1)/2)! 通りあります. このうち,以下の条件を満たす方法が何通りあるかを 998244353 で割った余りを求めてください.
- 各 i=2,3,\cdots,N について,A_i 回目の操作が終わった段階で,サーバー i にレシピが保存されている.
制約
- 2 \leq N \leq 13
- 1 \leq A_i \leq N(N-1)/2
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
N A_2 A_3 \cdots A_N
出力
答えを出力せよ.
入力例 1
3 1 3
出力例 1
2
例えば,以下のような操作は条件を満たします.
- 1 回目の操作: サーバー 1 と 2 を選ぶ.新たにサーバー 2 にレシピが保存される.
- 2 回目の操作: サーバー 2 と 3 を選ぶ.新たにサーバー 3 にレシピが保存される.
- 3 回目の操作: サーバー 1 と 3 を選ぶ.
入力例 2
3 1 1
出力例 2
0
入力例 3
4 1 2 6
出力例 3
48
入力例 4
13 62 20 56 74 2 32 20 2 41 27 22 44
出力例 4
665691201