この問題は vocabulary と同じ内容ですが、制約と出力する値が異なります。

問題

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

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

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

制約

$1 \leq N < 10^{100}$

入力

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

出力

作れる文の数を $10^{18}$ で割った余りを標準出力に出力してください。

サンプル

2

4

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

• $w_1$
• $w_1 w_2$
• $w_2$
• $w_2 w_1$

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

256

209024691848723456