C - Monotonically Non-Decreasing Sequences

配点 : 100点

個の整数 があります。

の順列 であって次の条件を満たすものの個数を求めてください：

• なる任意の整数 について、次が成り立つ：

ただし、答えは非常に大きくなる場合があるので、 で割ったあまりを出力してください。

• 入力はすべて整数である。

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

答えを求め、 で割ったあまりを標準出力へ出力せよ。

3
3 1 5

1

のみが条件を満たします。

5
3 1 4 1 5

2

のとき、またこのときに限り、条件が満たされます。

9
1 4 1 4 2 1 3 5 6

12