BoB004-E: Sorted Permutation

2 secs 1024 MB
kyaneko999

問題


Sakky さんは から までの番号がついた 体のプラモデルを持っています. 番目のプラモデルの高さは です.
あなたは Sakky さんに の順列 つ与えます.
を受け取った Sakky さんは,番号が左から順に となるように 体のプラモデルを横一列に並べます.
横一列に並べられたプラモデルの高さが,左から単調非減少になるような順列 は何通りあるでしょうか.

答えは非常に大きくなる可能性があるため, で割った余りを求めてください.

なお,プラモデルの高さが左から単調非減少になるような順列 とは,厳密には以下の条件を満たす のことを指します.

  • すべての に対して が成り立つ.

制約


  • 入力はすべて整数

入力


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


出力


答えを整数で出力しなさい.

入出力例


入力例1
4
1 2 2 3
出力例1
2

が条件を満たします.

入力例2
5
1 1 1 1 1
出力例2
120

すべての順列が条件を満たします.

提出


Go (1.14)