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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
typedef pair<long long, long long> KEY;
typedef map<KEY, long long> AUG;

AUG augm;


long long ffib(long long n, long long mod){
        if((n==0)||(n==1)) return n;
        AUG::iterator i = augm.find(KEY(n,mod));
        if(i!=augm.end()) return (*i).second;
        long long res;
        if((n+1)%2){
            long long nn = ffib(n/2, mod);
            long long n_minus_1 = ffib(n/2-1, mod);
            res = (2*n_minus_1+nn)%mod;
            res = (res*nn)%mod;

        } else {
           long long nn = ffib(n/2, mod);
           long long n_plus_1 = ffib(n/2+1, mod); 
           res = (nn*nn)%mod;
           res += (n_plus_1*n_plus_1)%mod;
           res = res%mod;
        }
        augm[KEY(n,mod)]=res;
        return res;
}

long long find_some(long long beg, long long step, long long limit, long long mod, long long what){
    long long j;
    for(long long i=0; (j=beg+i*step)<limit; i++){
        long long fb=ffib(j,mod);
        if(fb==what%mod) return j;
    }
    return limit;
}

vector<long long> find_all(long long beg, long long step, long long limit, long long mod, long long what){
    vector<long long> v;
    long long fnd;
    while((fnd=find_some(beg, step, limit, mod, what))<limit){
        v.push_back(fnd);
        beg=fnd+step;
    }
    return v;
}

struct _check{
    long long pw;
    long long nm;
    _check(long long p, long long n):pw(p), nm(n){};
    bool operator()(long long a){
        return ffib(a,pw)==nm%pw;
    }
};

long long logpw(long long pw5, long long coeff){
    return 4*pw5/5;
}

long long check(long long number){
    long long power = 1;
    long long uper = 10;
    while(number>uper){power++; uper*=10;}
    
    long long pw5=5;
    long long delim=6;
    long long beg=1;
    long long pw2=2;
    long long step=1;
    
    vector<long long> sfar;
    sfar.push_back(beg);
    for(long long pw=1; pw<=power; pw++){
        // find period on this level
        long long perd = find_some(beg,step,beg+delim, pw5, 0);
        long long coeff=ffib(perd-1, pw5);
        long long tms = logpw(pw5, coeff);
        long long delim=tms*perd+1;
        vector<long long> temp;
        for(vector<long long>::iterator i = sfar.begin(); i!=sfar.end(); i++){
                vector<long long> found = find_all(*i, step, delim, pw5, number);
                for(vector<long long>::iterator j = found.begin(); j!=found.end(); j++){
                    temp.push_back(*j);
                }       
        }
        if(temp.empty()) return -1;
        sfar.erase(sfar.begin(), sfar.end());
        for(vector<long long>::iterator i = temp.begin(); i!=temp.end(); i++){
            if(_check(pw2, number)(*i)) sfar.push_back(*i);
        }
        if(sfar.empty()) return -1;
        beg = perd;
        pw2 *= 2;
        pw5 *= 5;
        step = perd;
    }
    if(sfar.empty()) return -1;
    return sfar[0];
}

void myfunction(long long l){
    cout<<" "<<l<<" ";
}

int main(){
    long long n;
    cin>>n;
    long long res = check(n);
    if(res<0) cout<<"NIE"; else cout<<res;
}