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
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef unsigned long long ull;
typedef vector<ull> ullv;
typedef ullv::iterator ullvi;
const ull M=1000000000000000000ull;
const ull ULL_MAX=0xffffffffffffffffull;
ull mul(ull a,ull b){
    ull r=0,t;
    if(b>=M){if(M>ULL_MAX/2u)b-=M;else b%=M;}
    while(a){
        if(a&1){if(b>=M-r)r-=M;r+=b;}
        a>>=1;t=b;if(b>=M-b)t-=M;b+=t;
    }
    return r;
}
void mul22(ull io[2][2],ull m[2][2]){
    ull io00=mul(io[0][0],m[0][0])+mul(io[0][1],m[1][0]);
    ull io01=mul(io[0][0],m[0][1])+mul(io[0][1],m[1][1]);
    ull io10=mul(io[1][0],m[0][0])+mul(io[1][1],m[1][0]);
    ull io11=mul(io[1][0],m[0][1])+mul(io[1][1],m[1][1]);
    io[0][0]=io00%M;io[0][1]=io01%M;io[1][0]=io10%M;io[1][1]=io11%M;
}
void pow22(ull io[2][2],ull n){
    ull m[2][2]={{1,1},{1,0}};
    if(n<2)return;
    pow22(io,n>>1);
    mul22(io,io);
    if(n&1)mul22(io,m);
}
ull fib(ull n){
    ull m[2][2]={{1,1},{1,0}};
    if(!n)return 0;
    pow22(m,n-1);
    return m[0][0];
}
ull sol(size_t d,ull b,ull *r){
    ull f[1500],m,st,tr,i;size_t dd;ullv cl,ncl;
    if(d==1){st=60;m=10;tr=0;}else if(d==2){st=300;m=100;tr=7;}else{st=1500;m=1000;tr=12;}
    f[0]=0;f[1]=1;for(ull i=2;i<st;++i)f[i]=(f[i-1]+f[i-2])%M;
    if(d<=3){for(i=tr;i<st;++i)if(f[i]%m==b){*r=i;return 0;}return -1;}
    else{
        for(i=0;i<st;++i)if(f[i]%m==b%m)cl.push_back(i);
        dd=4;m=10000;
        while(dd<=d&&!cl.empty()){
            ncl.clear();
            for(ullvi ic=cl.begin();ic!=cl.end();++ic){
                ull nt=0;
                for(int e=0;e<11;++e){
                    ull ni=*ic+nt;ull nf=fib(ni);
                    if(nf%m==b%m)ncl.push_back(ni);
                    nt+=st;
                }
            }
            cl.swap(ncl);
            m*=10;st*=10;
            if(!cl.empty())++dd;
        }
        if(dd>d){*r=cl.back();return 0;}else return -1;
    }
}
int main(){
    char n[32];ull x;
    scanf("%s",n);sscanf(n,"%llu",&x);
    return!sol(strlen(n),x,&x)?!printf("%llu\n",x):!printf("NIE\n");
}