这题其实是上次模拟赛 A 的弱化版。

（下面式子的 $=$ 都指膜 $10^9+9$ 意义下的同余）

我们考虑 $5$ 在 $\mod 10^9+9$ 的时候是有二次剩余的，所以看到通项公式：

$$\frac{1}{\sqrt 5}\left((\frac{\sqrt 5+1}{2})^n - (\frac{\sqrt 5-1}{2})^n\right) = x$$

我们考虑设 $a = \frac{\sqrt 5+1}{2}$ ，那么有

$$a^n - (-\frac{1}{a})^n = (2a-1)x$$

然后分 $n$ 的奇偶性讨论。这里假设 $n$ 为奇

$$a^{2n}-(2a-1)xa^n + 1 = 0$$ $$a^n = \frac{(2a-1)x\pm \sqrt{(2a-1)^2x^2-4}}{2}$$

如果 $(2a-1)^2 - 4$ 莫有二次剩余，显然在 $n$ 为奇的时候无解。

否则，我们可以通过 BSGS 解出最小的 $n$ 。

当然，也可以从开始就上矩阵 BSGS 。。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include"ctime"
#include "queue"
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define min( a , b ) ( (a) < (b) ? (a) : (b) )
#define max( a , b ) ( (a) > (b) ? (a) : (b) )
typedef long long ll;
using namespace __gnu_pbds;

int P = 1000000009;

namespace QR {
    int i2 , P;

    void init( ) {
        srand( time( 0 ) );
    }

    struct comp {
        int a, b;

        comp(int a, int b) : a(a), b(b) {}
    };

    comp operator*(comp a, comp b) {
        return comp((1ll * a.a * b.a % P + 1ll * a.b * b.b % P * i2 % P) % P,
                    (1ll * a.a * b.b % P + 1ll * a.b * b.a % P) % P);
    }

    comp Pow(comp a, int x) {
        comp ans(1, 0);
        while (x) {
            if (x & 1) ans = ans * a;
            a = a * a, x >>= 1;
        }
        return ans;
    }

    int getit( int n , int p ) {
        P = p;
        if (n == 0) return 0;
        if (P == 2 && n == 1) return 1;
        if (n >= P || Pow(comp(n, 0), (P - 1) / 2).a == P - 1) return -1;
        int t;
        for (t = rand() % P + 1;; t = rand() % P + 1) {
            i2 = (1ll * t * t % P - n + P) % P;
            if (Pow(comp(i2, 0), (P - 1) / 2).a != P - 1) continue;
            break;
        }
        comp ans = Pow(comp(t, 1), (P + 1) / 2);
        return min(ans.a, P - ans.a);
    }
}
/*
 * 0 : answer is 0
 * -1 : no answer
 * answer is ret , P - ret
 */

vi S;
inline int BSGS(int A, int B, bool flag) {
    if (B == -1) return -1;
    gp_hash_table<int, int> s;
    if (flag && B % P == 1) return 0; s.clear();
    int m = ceil(sqrt(P)), ls = 1;
    for (int i = 0; i < m; i++, ls = (ll)ls * A % P)
        s[(ll)B * ls % P] = i;
    for (int i = m, t = ls; i <= P; i += m, t = (ll)t * ls % P)
        if (s[t]) return i - s[t];
    return -1;
}

inline void BSGS1(int A, int B) {
    int t = BSGS(A, 1, 0), a = BSGS(A, B, 1);
    if (a == -1) return;
    S.push_back(a);
    if (t != -1 && t % 2 == 1) S.push_back(( a + t ) % P);
}

int inv2;

inline int solve(int T, int x) {
    int A = QR::getit(((ll)x * x + 4) % P , P), B = QR::getit(((ll)x * x - 4 + P) % P , P), res = -1;
    if (A != -1) {
        int a = ((ll)x + A) * inv2 % P, b = ((ll)x - A + P) * inv2 % P;
        S.clear(), BSGS1(T, a), BSGS1(T, b);
        for( int i = 0 , t ; i < S.size() ; ++ i ) {
			t = S[i];
			if (t % 2 == 0) {
                if (res == -1) res = t;
                res = min(res, t);
            }
		}
    }
    if (B != -1) {
        int a = ((ll)x + B) * inv2 % P, b = ((ll)x - B + P) * inv2 % P;
        S.clear(), BSGS1(T, a), BSGS1(T, b);
        for( int i = 0 , t ; i < S.size() ; ++ i ){
			t = S[i];
			if (t % 2 == 1) {
                if (res == -1) res = t;
                res = min(res, t);
            }
		}
    }
    return res;
}

inline int solve1(int x, int sqrt5) {
    x = (ll)x * sqrt5 % P; int T = (ll)(sqrt5 + 1) * inv2 % P;
    return solve(T, x);
}

void solve( ) {
    QR::init();
    srand( 114514 );
    int x; scanf("%d", &x), inv2 = (P + 1) / 2;
    int sqrt5 = QR::getit(5 , P);
    int A = solve1(x, sqrt5);
    printf("%d\n",A);
}

signed main() {
//    int T; cin >> T;
//    while (T--) solve();
    solve();
    return 0;
}