東大理系数学1998後期第3問改

2 secs 1024 MB
googol_S0

respect:東大文系数学2021第2問改東大文系数学2020第2問改

問題文


正の整数 が与えられます。次のような操作を考えます。

  • まず、整数列 を持ちます。最初、これは です。
  • 回次の操作を行います。
    • の好きな位置に を挿入し、その に隣り合う各要素を、 ならば に、 ならば に置き換える。

回の操作として考えられるものは 通りありますが、このうち操作を終えた後の の全ての要素が であるようなものの個数を で割った余りを求めてください。

制約


  • は整数

入力


N

出力


条件を満たす操作の個数を で割った余りを出力してください。

サンプル


入力1
3
出力1
2

条件を満たす操作の一例を示します。なお、挿入された を赤色、隣り合って置き換えられた要素を青色で示しています。

  • の先頭に を挿入します。操作後の となります。
  • の末尾に を挿入します。操作後の となります。

この場合の答えは です。

入力2
5
出力2
0

この場合の答えは です。

入力3
7
出力3
160

条件を満たす操作での の変化の一例を示します。

入力4
1998
出力4
928752812

答えを で割った余りを求めてください。

提出


Go (1.14)