(特別)フィボナッチ数列の性質③

フィボナッチ数列の各項を自然数 $n$ で割った余りを並べる数列を考えよう。これを「$\bmod\ n$ の数列」と呼ぶことにする。

例えば，$\bmod\ 2$ の数列は

$1,\ 1,\ 0,\ 1,\ 1,\ 0,\ 1,\ldots$

であり，$\bmod\ 3$ の数列は

$1,\ 1,\ 2,\ 0,\ 2,\ 2,\ 1,\ 0,\ 1,\ 1,\ 2,\ 0,\ldots$

である。

すると，どちらの数列もある一定の数の並びが繰り返されている事が分かる（他の数列でも試してみよう）。この繰り返しの単位における数の個数を「周期」と呼ぶことにする。

$\bmod\ 2$ の数列は“ $1,\ 1,\ 0$ ”が繰り返されていて，周期は3である。$\bmod\ 3$ の数列は“ $1,\ 1,\ 2,\ 0,\ 2,\ 2,\ 1,\ 0$ ”が繰り返されていて，周期は8である。

ここで，$\bmod\ n$ の数列の周期を求めよう。

問題文

次の問いに答えよ。ただし，フィボナッチ数列の第 $n$ 項を $F_n$ とする。

1. $2$ つの自然数の組 $(i,\ j)$ に対して，$F_i$ を $j$ で割った余りを出力する関数 FiboMod を作成せよ。
2. 与えられた自然数 $n$ に対して，$\bmod\ n$ の数列の周期を出力せよ。

ただし，必要であれば問題「フィボナッチ数列の性質①」で作成した関数 Fibonacci を利用しても構わない。利用する場合は，Fibonacci(n) の制約が $1\leqq \mathtt{n}\leqq 46$であったことに注意すること。

一般に $\bmod\ n$ の数列の周期を求める数式は発見されておらず，そのような数式は存在しないのではないかという予想が立てられている（ウォール予想）が，現在も未解決問題となっている。

制約

• 入力はすべて自然数
• $2\leqq n\leqq 200$

入力

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

出力

答えの値 $A$ を以下の形式で出力してください。

サンプル１

11

10

$\bmod\ 11$の数列は

$\underbrace{1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 2,\ 10,\ 1,\ 0}_{繰り返される},\ 1,\ 1,\ 2,\ 3,\ldots$

となっているので，周期は10です。

サンプル２

150

600

関数 FiboMod に関するヒント

関数 FiboMod を，関数 Fibonacci を使用して作成すると，第46項以降を正しく出力することができません。これは，Fibonacci(n) が $\mathtt{n}\geqq 46$ のときにオーバーフローして正しい値を出力することができないためです。

つまり，関数 Fibonacci を使って関数 FiboMod を作成することはできないということです。

ではどうすればよいかというと，関数 Fibonacci の骨格はそのままにオーバーフローしないように関数 FiboMod を作成すればよいのです。そのためには，次の性質を使います。

それでは，Good Luck!