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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cassert>

typedef long long ll;

using namespace std;

ll power10[20];
ll tentoi(int i) {
   return power10[i];
}

// ****** FIBONACCI COMPUTATION BLOCK ***************

void multiply(ll F[2][2], ll M[2][2], int i);
void power(ll F[2][2], ll pow, int i);

/* F_k mod 10^i */
ll fib(ll k, int i) {
  ll F[2][2] = {{1,1},{1,0}};
  if (k == 0) return 0;
  power(F, k-1, i);
  return F[0][0];
}

/* F^pow mod 10^i */
void power(ll F[2][2], ll pow, int i) {
  if( pow == 0 || pow == 1) return;
  ll M[2][2] = {{1,1},{1,0}};
  power(F, pow/2, i);
  multiply(F, F, i);
  if (pow%2 != 0) multiply(F, M, i);
}

/* a*b mod 10^18 */
ll mul(ll a, ll b) {
   ll t18=tentoi(18); ll t9=tentoi(9);
   ll a1=a/t9; ll b1=b/t9;
   ll a2=a%t9; ll b2=b%t9;
   ll y=a2*b2;
   ll z= (a1*b2) + (a2*b1) ;
   z %= t9;
   z*=t9;
   return ( y + z ) %t18;
}

/* mnozenie macierzy long longow 2x2 mod 10^i */
void multiply(ll F[2][2], ll M[2][2], int i) {
  ll x =  mul(F[0][0],M[0][0]) + mul(F[0][1],M[1][0]);
  ll y =  mul(F[0][0],M[0][1]) + mul(F[0][1],M[1][1]);
  ll z =  mul(F[1][0],M[0][0]) + mul(F[1][1],M[1][0]);
  ll w =  mul(F[1][0],M[0][1]) + mul(F[1][1],M[1][1]);

  F[0][0] = x%tentoi(i);
  F[0][1] = y%tentoi(i);
  F[1][0] = z%tentoi(i);
  F[1][1] = w%tentoi(i);
}

// ******************************************

// actual code starts here ***********
ll can[10]; int cSize;
ll canFu[10]; int cFuSize;

// period of F_k mod 10^i
ll period(int i) {
   assert(i>0);
   if(i==1) return 60;
   if(i==2) return 300;
   return 15*tentoi(i-1);
}

void FindCandidates(int i, ll n) {
   cSize=0; ll p=period(i);
   n%=tentoi(i);
   ll f=0, g=1; ll next;
   for(ll j=0; j<p; ++j) {
      if( f==n ) can[cSize++]=j;
      next=(f+g)%tentoi(i);
      f=g;
      g=next;
   }
}

void FindCandidatesFu(int i, int j, ll n) {
   ll jump=period(i);
   ll no_jumps=tentoi(j-i);
   n%=tentoi(j);

   cFuSize=0;
   for(int k=0; k<cSize; ++k) {
       ll curCan=can[k];
       for(int jum=0; jum<no_jumps; ++jum) {
          if( fib(curCan,j)==n ) canFu[cFuSize++]=curCan;
          curCan+=jump;
       }
   }
}

int main() {
    // tablicowanie poteg 10
    power10[0]=1; for(int i=1; i<20; ++i) power10[i]=10*power10[i-1];

    string s;
    getline(cin,s);
    int len=s.size(); // maks 18
    ll n = stoll(s,nullptr,10);

    int treshold=4; int step=1;

    if(len <= treshold) {
        FindCandidates(len,n);
        if(cSize > 0) //cout << "TAK" << endl;
           cout << can[0]+period(len) << endl;
        else cout << "NIE" << endl;
        return 0;
    }

    FindCandidates(treshold,n);

    treshold+=step;
    while(len > treshold) {
       FindCandidatesFu(treshold-step,treshold,n);
       cSize=cFuSize;
       for(int i=0; i<cSize; ++i) can[i]=canFu[i];
       treshold+=step;
    }

    FindCandidatesFu(treshold-step,len,n);

    if(cFuSize > 0) //cout << "TAK" << endl;
       cout << canFu[0]+period(len) << endl;
    else cout << "NIE" << endl;

    return 0;
}