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
90
#include<bits/stdc++.h>
#define rep(i,k,n) for(int i= (int) k;i< (int) n;i++)
#define pb push_back
#define ft first
#define sd second
typedef long long ll;
const long long inf = 9223372036854775807ll;
const int iinf = 2147483647;
const int limit = 1048576;
using namespace std;
bool sync_with_stdio (bool sync = false);

ll mod = 1;

vector<vector<ll> > operator *(const vector<vector<ll> >& a, const vector<vector<ll> >& b)
{
    vector<vector<ll> > res(a.size(), vector<ll>(a.size(), 0));
    rep(i, 1, a.size()) rep(k, 1, a.size()) rep(j, 1, a.size())
    {
        res[i][j] =  (res[i][j] + a[i][k] * b[k][j]) % mod;
    }
    return res;
}

vector<vector<ll> > pow(vector<vector<ll> > a, ll p)
{
    vector<vector<ll> > res = a;
    p -= 1;
    while(p)
    {
        if(p % 2)
            res = res * a;
        a = a * a;
        p /= 2;
    }
    return res;
}

ll Fib(ll n)
{
    if(n == 0)
        return 0;
    vector<vector<ll > > a = {{0, 0, 0}, {0, 0, 1}, {0, 1, 1}};
    a = pow(a, n);
    return a[1][2];
}

int main()
{
    string s;
    cin >> s;
    ll rem = 0, per;
    vector<ll> cands;
    while(s.size())
    {
        vector<ll> new_cands;
        rem += mod * (s.back() - '0');
        s.pop_back();
        mod *= 10;
        if(mod == 10)
        {
            rep(i, 0, 60)
            if(Fib(i) == rem)
                new_cands.pb(i);
            per = 60;
        }
        if(mod == 100 || mod == 1000)
        {
            rep(i, 0, 5)
            rep(j, 0, cands.size())
            if(Fib(per * i + cands[j]) == rem)
                new_cands.pb(per * i + cands[j]);
            per *= 5;
        }
        if(mod >= 10000)
        {
            rep(i, 0, 10)
            rep(j, 0, cands.size())
            if(Fib(per * i + cands[j]) == rem)
                new_cands.pb(per * i + cands[j]);
            per *= 10;
        }
        swap(cands, new_cands);
    }
    if(cands.size())
        cout << cands[0];
    else
        cout << "NIE";
    return 0;
}