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
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;

template<typename T>
inline T pow2(int e) { return T(1) << e; }

struct M22
{
  M22(i64 a11, i64 a12, i64 a21, i64 a22) : a11_(a11), a12_(a12), a21_(a21), a22_(a22) {}
  
  i64 a11_, a12_, a21_, a22_;
};

u64 mltp64(u64 x, u64 y, u64 m)
{
  if (x == 0 || y == 0) return 0;
  int t[18];
  int k = 0;
  while (x != 0)
  {
    t[k++] = x%10;
    x /= 10;
  }
  u64 r = 0;
  for (int i=k-1; i>=0; --i)
  {
    r = (r*10) % m;
    r = (r + y*t[i]) % m;
  }
  return r;
}

M22 multiply(const M22& x, const M22& y, i64 m)
{
  return M22((mltp64(x.a11_,y.a11_,m) + mltp64(x.a12_,y.a21_,m)) % m,
             (mltp64(x.a11_,y.a12_,m) + mltp64(x.a12_,y.a22_,m)) % m,
             (mltp64(x.a21_,y.a11_,m) + mltp64(x.a22_,y.a21_,m)) % m,
             (mltp64(x.a21_,y.a12_,m) + mltp64(x.a22_,y.a22_,m)) % m);
}

M22 pow(const M22& x, u64 e, i64 m)
{
  M22 y(1,0,0,1);
  if (e == 0) return y;
  for (int i=63-__builtin_clzll(e); i>=0; --i)
  {
    y = multiply(y,y,m);
    if (e & pow2<u64>(i)) y = multiply(y,x,m);
  }
  return y;
}

i64 fib(i64 n, i64 m)
{
  return pow(M22(0,1,1,1), n, m).a12_;
}

i64 solve(i64 r, int n)
{
  i64 p10 = 1000;
  if (n == 1) p10 = 10;
  else if (n == 2) p10 = 100;
  i64 p15 = 1500;
  i64 r10 = r%p10;
  vector<i64> qs;
  for (i64 i=0; i<p15; ++i)
    if (fib(i, p10) == r10) qs.push_back(i);
  for (int i=4; i<=n; ++i)
  {
    p10 *= 10;
    r10 = r%p10;
    vector<i64> nqs;
    for (i64 q : qs)
      for (int j=0; j<10; ++j)
        if (fib(p15*j+q, p10) == r10) nqs.push_back(p15*j+q);
    p15 *= 10;
    qs = move(nqs);
  }
  if (qs.empty()) return -1;
  return qs[0] + 1500000000000000000ll;
}

int main()
{
  char tmp[20];
  scanf("%s", tmp);
  string s(tmp);
  i64 q = solve(atoll(s.c_str()), (int)s.size());
  if (q == -1) printf("NIE\n");
  else printf("%lld\n", q);
}