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
#include <bits/stdc++.h>

using namespace std;

int64_t powerOfTen[19];

struct matrix {
  matrix() 
    : values { {0, 0}, {0, 0} } {}
  int64_t values[2][2];
};

int64_t multiply(int64_t a, int64_t b, int modExponent) {
  int halfExponent = (modExponent + 1) / 2;
  int64_t base = powerOfTen[halfExponent];
  int64_t aBig = a / base, aSmall = a % base;
  int64_t bBig = b / base, bSmall = b % base;
  return (((aSmall * bBig + aBig * bSmall) % base) * base + aSmall * bSmall) % powerOfTen[modExponent];
}

matrix multiply(const matrix& a, const matrix& b, int modExponent) {
  matrix result;
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        result.values[i][j] = (result.values[i][j] + multiply(a.values[i][k], b.values[k][j], modExponent)) % powerOfTen[modExponent];
      }
    }
  }
  return result;
}

matrix power(const matrix& a, int64_t exponent, int modExponent) {
  matrix result;
  result.values[0][0] = result.values[1][1] = 1;
  matrix multiplier = a;
  while (exponent > 0) {
    if (exponent % 2 == 1) {
      result = multiply(result, multiplier, modExponent);
    }
    multiplier = multiply(multiplier, multiplier, modExponent);
    exponent /= 2;
  }
  return result;
}

int64_t fibonacci(int64_t index, int modExponent) {
  matrix fibonacciMatrix;
  fibonacciMatrix.values[0][0] = fibonacciMatrix.values[0][1] = fibonacciMatrix.values[1][0] = 1;
  return power(fibonacciMatrix, index, modExponent).values[0][1];
}

void initialize() {
  powerOfTen[0] = 1;
  for (int i = 1; i <= 18; i++) {
    powerOfTen[i] = powerOfTen[i-1] * 10;
  }
}

int main() {
  initialize();

  string input;
  int64_t remainder;
  vector<int64_t> indices[2];

  cin >> input;
  int length = input.length();
  stringstream stream;
  stream << input;
  stream >> remainder;

  for (int i = 0; i < 60; i++) {
    if (fibonacci(i, 1) % 10 == remainder % 10) {
      indices[1].push_back(i);
    }
  }

  for (int i = 2; i <= length; i++) {
    indices[i % 2].clear();
    int64_t wanted = remainder % powerOfTen[i];
    for (int64_t index : indices[(i + 1) % 2]) {
      for (int64_t candidate = index; candidate < 6 * powerOfTen[i]; candidate += 6 * powerOfTen[i - 1]) {
        if (fibonacci(candidate, i) == wanted) {
          indices[i % 2].push_back(candidate);
        }
      }
    }
  }
  if (indices[length % 2].empty()) {
    cout << "NIE" << endl;
  } else {
    uint64_t result = indices[length % 2][0];
    result += 6 * powerOfTen[18];
    cout << result << endl;
  }
}