1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstdio>
#include <vector>
#include <climits>
using namespace std;
#define ll unsigned long long

ll mod = 1e18;

ll mul(ll a, ll b) {
    if(mod <= 1e9)
        return (a * b) % mod;
    if(b > a) swap(a, b);
    ll res = 0, step = ULLONG_MAX / mod;
    while(b) {
        res = (res + a * (b % step)) % mod;
        a = (step * a) % mod;
        b /= step;
    }
    return res;
}

struct Matrix {
    ll a, b, c, d;
    Matrix(ll x = 0) {
        a = d = x;
        b = c = 0;
    }
    Matrix(ll a, ll b, ll c, ll d) : a(a), b(b), c(c), d(d) {}

    void operator*=(Matrix const& o) {
        (*this) = { (mul(a, o.a) + mul(b, o.c)) % mod,
                    (mul(a, o.b) + mul(b, o.d)) % mod,
                    (mul(c, o.a) + mul(d, o.c)) % mod,
                    (mul(c, o.b) + mul(d, o.d)) % mod };
    }

    void print() {
        printf("%3lld %3lld\n%3lld %3lld\n", a, b, c, d);
    }
};

ll fib(ll b) {
    Matrix res(1);
    Matrix a;
    a.c = a.b = a.a = 1;
    while(b) {
        if(b & 1) res *= a;
        a *= a;
        b /= 2;
    }
    return res.b;
}

ll t[20];

int main() {
    int n = 0; ll k = 0;
    char input[20];
    scanf("%s", input);
    while(input[n] != '\0') {
        k = 10 * k + input[n] - '0';
        n++;
    }

    t[1] = 60; t[2] = 300; t[3] = 1500;
    for(int i = 4; i <= n; ++i) t[i] = 10 * t[i - 1];
    mod = 1;
    ll cycle = 1;
    vector<ll>propose = { 1 };
    vector<ll>tmp;
    for(int i = 1; i <= n; ++i) {
        mod *= 10;
        for(ll a: propose) {
            for(ll _n = a; _n <= t[i]; _n += cycle)
                if(fib(_n) == k % mod)
                    tmp.push_back(_n);
        }
        cycle = t[i];
        propose.swap(tmp);
        tmp.clear();
    }
    if(propose.size()) {
        if(propose[0] < 100)
            propose[0] += t[n];
        printf("%llu\n", propose[0]);
    }
    else printf("NIE\n");
    return 0;
}