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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

typedef unsigned long long int BigInt;

constexpr BigInt mod = 1000llu * 1000llu * 1000llu
                     * 1000llu * 1000llu * 1000llu;  // 10**18

BigInt SumModulo(BigInt a, BigInt b) {
  return (a + b) % mod;
}

BigInt MultiplicationModulo(BigInt a, BigInt b) {
  BigInt result = 0llu;
  while (a > 0) {
    if (a % 2 == 1) {
      result = SumModulo(result, b);
    }
    b = (b * 2) % mod;
    a /= 2;
  }
  return result;
}

constexpr BigInt Power(BigInt base, int exponent) {
  return exponent == 0 ? 1llu : base * Power(base, exponent - 1);
}

struct Matrix {
  BigInt a00_, a01_, a10_, a11_;

  Matrix(BigInt a00, BigInt a01,
         BigInt a10, BigInt a11) : a00_(a00), a01_(a01), a10_(a10), a11_(a11) {}

  Matrix(const Matrix& matrix) = default;
  Matrix(Matrix&& matrix) = default;
  Matrix& operator=(const Matrix& matrix) = default;

  Matrix operator * (const Matrix& matrix) const {
    return Matrix(
        SumModulo(
            MultiplicationModulo(a00_, matrix.a00_),
            MultiplicationModulo(a01_, matrix.a10_)),
        SumModulo(
            MultiplicationModulo(a00_, matrix.a01_),
            MultiplicationModulo(a01_, matrix.a11_)),
        SumModulo(
            MultiplicationModulo(a10_, matrix.a00_),
            MultiplicationModulo(a11_, matrix.a10_)),
        SumModulo(
            MultiplicationModulo(a10_, matrix.a01_),
            MultiplicationModulo(a11_, matrix.a11_)));
  }
};

const int max_power = 105;
std::vector<Matrix> all_powers;  // On i-th position is Fib_matrix^(2^i).

void PrepareAllPowers() {
  all_powers.emplace_back(0, 1,
                          1, 1);  // Fib_matrix.
  for (int i = 1; i < max_power; i++) {
    all_powers.emplace_back(all_powers[i - 1] * all_powers[i - 1]);
  }
}

BigInt Fibonacci(BigInt f) {
  Matrix result(1, 0,
                0, 1);
  int exponent = 0;
  while (f > 0) {
    if (f % 2 == 1) {
      result = result * all_powers[exponent];
    }
    exponent++;
    f /= 2;
  }
  return result.a10_;
}

char number_as_string[18 + 5];
BigInt number;
int n;

constexpr int small = 3;
constexpr BigInt small_limit = Power(10, small);
constexpr BigInt small_cycle_length = small_limit * 15;
BigInt limit = small_limit;
BigInt fibonacci[small_cycle_length + 5];

void dfs(int depth, BigInt index, BigInt limit, BigInt cycle) {
  if (Fibonacci(index) % limit == number % limit) {
    if (depth >= n) {
      throw index;
    }
    const BigInt next_limit = limit * 10;
    const BigInt next_cycle = cycle * 10;
    for (int i = 0; i < 10; i++) {
      dfs(depth + 1, index += cycle, next_limit, next_cycle);
    }
  }
}

int main() {
  scanf("%s", number_as_string);
  n = strlen(number_as_string);
  sscanf(number_as_string, "%llu", &number);
  limit = std::min(limit, Power(10, n));

  PrepareAllPowers();

  fibonacci[0] = 0llu;
  fibonacci[1] = 1llu;
  try {
    for (int i = 0; i < small_cycle_length; i++) {
      if (i >= 2) {
        fibonacci[i] = SumModulo(fibonacci[i - 2], fibonacci[i - 1]);
      }
      if (fibonacci[i] % limit == number % limit) {
        dfs(small, i, limit, small_cycle_length);
      }
    }
    printf("NIE\n");
  } catch (BigInt answer) {
    printf("1500000000000000000000000000000000000000%llu\n", answer);
  }
  return 0;
}