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
#include <iostream>
#include <vector>

struct Periods10 {
  long long P[20];
  Periods10() {
    P[0] = 1LL; P[1] = 60LL; P[2] = 300LL; P[3] = 1500LL;
    for(int i=4;i<=18;++i) P[i] = P[i-1]*10LL;
  }
  long long get(int i) {return P[i];}
};


long long mult(long long a, long long b,long long m){
  return a?(a%2*b+mult(a/2,2*b%m,m))%m:0LL;
}

long long rA,rB;
long long a,b;
void find_fib(long long k,long long m){
  if(k==0) {rA=0; rB=1; return;}
  find_fib(k/2,m);
  a = mult((m-rA+2*rB)%m,rA,m);        // = (m-a+2*b)%m*a%m;
  b = (mult(rB,rB,m)+mult(rA,rA,m))%m; // = (b*b%m+a*a%m)%m;
  if(k%2==0){rA = a; rB = b;}
  else{rA = b; rB = (a+b)%m;}
}

// finds Fib_k mod m
long long fib(long long k,long long m){
  find_fib(k,m);
  return rA;
}

char C[20];

int main(){
  Periods10 per;
  int n;
  long long c;
  std::cin>>C;
  for(c = n = 0;C[n];++n)
    c = 10*c + C[n]-'0';
  long long m = 1;
  std::vector<long long> prev(0);
  std::vector<long long> cur(0);
  prev.push_back(0);
  for(int i=1;i<=n;++i){
    m*=10;
    for(long long e : prev)
      for(long long j = 0 ; j <per.get(i)/per.get(i-1); ++j){
        long long k = per.get(i-1)*j+e;
        if(fib(k,m) == c%m) cur.push_back(k);
      }
    prev = cur;
    cur.clear();
  }
  if(!prev.empty()) std::cout<< prev[0] << std::endl;
  else std::cout << "NIE" << std::endl;
  return 0;
}