Description

Fib数列为 $1,1,2,3,5,8,\dots$

求在 $\mod 10^9+9$ 的意义下，数字 $N$ 在 Fib 数列中出现在哪个位置。

无解输出 $-1$。

Input Format

一行，一个数字 $N$，$N\le10^9+9$

Output Format

如题

Sample

3

4