#P5104. Fib数列

    ID: 4190 传统题 1000ms 128MiB 尝试: 489 已通过: 134 难度: 8 上传者: 标签>CF2500提高+/省选-BSGSTonelli–Shanks 算法二次剩余模逆元快速幂奇偶性分析fib数

Fib数列

Description

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

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

无解输出 −1-1。

Input Format

一行,一个数字 NN,N≤109+9N\le10^9+9

Output Format

如题

Sample

3
4