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
91
92
93
94
95
96
97
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

typedef unsigned long long ll;
#define pb push_back
#define si size()

const int maxn=19;

ll mul(ll a, ll b, ll m){
    ll res=0;
    while(b){
        res+=a*(b%10);
        res%=m;
        a=(a*10)%m;
        b/=10;
    }
    return res;
}

void matrixMul(ll a[2][2], ll b[2][2], ll m){
    ll c[2][2];
    for(int i=0;i<2;++i)
        for(int j=0;j<2;++j){
            c[i][j]=0;
            for(int k=0;k<2;++k){
                c[i][j]+=mul(a[i][k], b[k][j], m);
                c[i][j]%=m;
            }
        }
    for(int i=0;i<2;++i)
        for(int j=0;j<2;++j)
            a[i][j]=c[i][j];
}

ll fib(ll n, ll m){
    ll a[2][2]={{1, 1}, {1, 0}};
    ll c[2][2]={{1, 0}, {0, 1}};
    while(n){
        if(n&1)
            matrixMul(c, a, m);
        n>>=1;
        matrixMul(a, a, m);
    }
    return c[1][0];
}

ll num(char *s){
    ll n=0;
    for(int i=0;s[i];++i)
        n=n*10+s[i]-'0';
    return n;
}

vector<ll> findProperFibNums(ll p[], ll q[], ll r, int n){
    vector<ll> V;
    ll a=0, b=1;
    for(int i=0;i<p[n];++i){
        if(a==r)
            V.pb(i);
        swap(a+=b, b);
        b%=q[n];
    }
    return V;
}

int main()
{
    ll p[maxn]={0, 60, 300, 1500};
    ll q[maxn]={1};
    for(int i=4;i<maxn;++i)
        p[i]=p[i-1]*10;
    for(int i=1;i<maxn;++i)
        q[i]=q[i-1]*10;
    char s[maxn];
    int n;
    ll r;
    scanf("%s", s);
    n=strlen(s);
    r=num(s);
    vector<ll> V=findProperFibNums(p, q, r%q[3], min(3, n));
    for(int i=4;i<=n;++i){
        vector<ll> Q;
        for(int j=0;j<V.si;++j)
            for(int k=0;k<10;++k)
                if(fib(V[j]+p[i-1]*k, q[i])==r%q[i])
                    Q.pb(V[j]+p[i-1]*k);
        V.clear();
        V=Q;
    }
    if(V.empty())
        printf("NIE");
    else printf("%llu", V[0]+p[n]);
}