問題


Moja くんは 個の単語を知っています。また、知っている単語を並べることで文を作ることができます。Moja くんが作れる文のうち、以下の条件を全て満たすものは何通りあるか求めてください。ただし、同じ単語の組み合わせを使用していてもその並べ方が異なる複数の文はそれぞれ区別します。

  • 文は つ以上の単語からなる。
  • 文は Moja くんが知っている単語のみからなる。
  • 文に同じ単語は 回以上出現しない。

Moja くんがたくさんの単語を知っているとき作れる文の数は非常に大きくなります。そのため、作れる文の数の代わりにそれを で割った余りを出力してください。

制約


入力


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

出力


作れる文の数を で割った余り ( 以上 以下の整数となります) を標準出力に出力してください。

サンプル


入力例1
2
出力例1
4

Moja くんは つの単語 ( とします) を知っています。このとき、

つの文を作ることができます。


入力例2
256
出力例2
23456

Submit


Go (1.14)