Період Фібоначчі

Послідовність цілих чисел

F_r = a_0, a_1, \ldots, a_n, \ldots,

називається послідовністю Фібоначчі за модулем $r$, якщо a_0 = 0, a_1 = 1, і для всіх i \geq 2 виконується a_i = (a_{i-2} + a_{i-1}) \bmod r.

Число p > 0 називається періодом послідовності, якщо існує таке i_0, що для всіх i \geq i_0 виконується a_i = a_{i+p}. Послідовність називається періодичною, якщо вона має період. Очевидно, що якщо послідовність періодична, то вона має найменший період.

Задано $r$, потрібно визначити, чи є послідовність F_r періодичною, і якщо так, то знайти її найменший період.