問題文


数列を、漸化式で定義する。で割った余りを求めよ。

制約


  • 入力は全て整数

入力


入力は以下の形式で与えられる。

n

出力


計算結果を1行に出力せよ。

サンプル


入力1
4
出力1
65536

となります。


入力2
5
出力2
683753077

オーバーフローに注意してください。

提出


Go (1.14)