斐波那契

题目描述

给定一个模$10^{13}$意义下的非负整数$a$，求$a$第一次出现在模$10^{13}$意义下的斐波那契数列$F$中的第几项。

这里模意义下的斐波那契数列$F$定义如下：

$F(0)=0$，$F(1)=1$，$F(n)=(F(n-1)+F(n-2)) \bmod 10^{13}$。

输入格式

一行一个非负整数$a$。

输出格式

一行一个整数$ans$，表示$a$第一次在数列$F$中出现的位置。

如果$a$不出现在数列$F$中，输出$-1$。

数据范围与提示

• 对于$10\%$的数据，保证$a$不会出现在数列$F$中；
• 对于另外$30\%$的数据，保证答案不超过$10^{7}$；
• 对于$100\%$的数据，保证$0 \leq a < 10^{13}$。

样例

1

1