Moja くんは 個の単語を知っています。また、知っている単語を並べることで文を作ることができます。Moja くんが作れる文のうち、以下の条件を全て満たすものは何通りあるか求めてください。ただし、同じ単語の組み合わせを使用していてもその並べ方が異なる複数の文はそれぞれ区別します。
Moja くんがたくさんの単語を知っているとき作れる文の数は非常に大きくなります。そのため、作れる文の数の代わりにそれを で割った余りを出力してください。
入力は標準入力から以下の形式で与えられます。
作れる文の数を で割った余り ( 以上 以下の整数となります) を標準出力に出力してください。
2
4
Moja くんは つの単語 ( とします) を知っています。このとき、
の つの文を作ることができます。
256
23456