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

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

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

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

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

• は整数

N

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

3

2

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

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

この場合の答えは です。

5

0

この場合の答えは です。

7

160

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

1998

928752812

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