Mujin Programming Challenge 2018

F - チーム分け


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 1024MB

配点 : 600

問題文

N 人を、それぞれの人がただ 1 つのチームに属するようにチーム分けを行います。

しかし、人によっては多くの人が属するチームに属したくないと考えています。

この条件は N 要素からなる整数列 a で表され、i 番目の人は a_{i} 人以下から成るチームに配属されることになります。

チーム分けをするに当たってこのようなチーム分けは何通り考えられるのかを計算したくなりました。答えは非常に大きくなることがあるので、998244353 で割ったあまりを出力してください。ただし、2 つのチーム分けが異なるとは、ある 2 人が存在して、片方のチーム分けでは同じチームに属するがもう片方のチーム分けでは違うチームに属する、という場合を表します。

制約

  • 1 \leq N \leq 1000
  • 1 \leq a_i \leq N
  • 入力は全て整数である

入力

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

N
a_1 a_2 ... a_{N-1} a_N

出力

条件を満たすチーム分けの方法の場合の数を 998244353 で割ったあまりを出力せよ。


入力例 1

1
1

出力例 1

1

1 人をチーム分けする方法は 1 通りです。


入力例 2

3
3 3 2

出力例 2

4

条件を満たすチーム分けは、((1),(2),(3)), ((1,2),(3)), ((1,3),(2)), ((2,3),(1))4 通りです。


入力例 3

10
3 1 4 1 5 9 2 6 3 10

出力例 3

1869

Submit提出する