Fibonacci Dövrü

Tam ədədlər ardıcıllığı

F_r = a_0, a_1, ..., a_n, ...,

əgər a_0 = 0, a_1 = 1 və bütün i ≥ 2 üçün a_i = (a_{i-2} + a_{i-1}) mod r olarsa, bu ardıcıllıq Fibonacci ardıcıllığı mod r adlanır.

Bir ədəd p > 0 ardıcıllığın dövrü adlanır, əgər elə bir i_0 varsa ki, bütün i ≥ i_0 üçün a_i = a_{i+p } bərabərliyi təmin olunur. Ardıcıllıq dövri adlanır, əgər onun dövrü varsa. Aydındır ki, əgər ardıcıllıq dövri olarsa, onun ən kiçik dövrü var.

Verilmiş r üçün F_r ardıcıllığının dövri olub-olmadığını və əgər dövri olarsa, onun ən kiçik dövrünü tapmalısınız.

Giriş verilənləri

Giriş faylı a_n tam ədəd r (2 ≤ r ≤ 2·10^9) ehtiva edir.

Çıxış verilənləri

Əgər F_r dövri olarsa, onun ən kiçik dövrünü çıxış faylına yazın. Əgər dövri deyilsə, 0 yazın.

Nümunələr