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

using namespace std;

const int kMaxLength = 18;
const long long kPisano = 1500LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;

long long Add(long long a, long long b, long long m) {
  return (a + b) % m;
}

// http://stackoverflow.com/questions/12168348/ways-to-do-modulo-multiplication-with-primitive-types
long long mulmod(long long a, long long b, long long m) {
    long long res = 0;
    while (a != 0) {
        if (a & 1) res = (res + b) % m;
        a >>= 1;
        b = (b << 1) % m;
    }
    return res;
}

class Transformation {
 public:
  Transformation() : a00_(0), a01_(1), a10_(1), a11_(1) {}

  long long a00() const { return a00_; }
  long long a01() const { return a01_; }
  long long a10() const { return a10_; }
  long long a11() const { return a11_; }

  static Transformation Multiply(const Transformation& a, const Transformation& b, const long long modulus) {
    return Transformation(
        Add(mulmod(a.a00(), b.a00(), modulus), mulmod(a.a01(), b.a10(), modulus), modulus),
        Add(mulmod(a.a00(), b.a01(), modulus), mulmod(a.a01(), b.a11(), modulus), modulus),
        Add(mulmod(a.a10(), b.a00(), modulus), mulmod(a.a11(), b.a10(), modulus), modulus),
        Add(mulmod(a.a10(), b.a01(), modulus), mulmod(a.a11(), b.a11(), modulus), modulus));
  }

  Transformation Power(const long long exponent, const long long modulus) const {
    if (exponent == 0) return Transformation(1, 0, 0, 1);
    Transformation half = Power(exponent / 2, modulus);
    Transformation full = Multiply(half, half, modulus);
    if (exponent % 2) return Multiply(full, *this, modulus); else return full;
  }

 private:
  Transformation(const long long a00, const long long a01, const long long a10, const long long a11) : a00_(a00), a01_(a01), a10_(a10), a11_(a11) {}

  long long a00_;
  long long a01_;
  long long a10_;
  long long a11_;
};

class State {
 public:
  State() : current_(0), next_(1) {}

  long long current() const { return current_; }

  State Apply(
      const Transformation& transformation, const long long modulus) const {
    return State(Add(mulmod(transformation.a00(), current_, modulus), mulmod(transformation.a01(), next_, modulus), modulus), Add(mulmod(transformation.a10(), current_, modulus), mulmod(transformation.a11(), next_, modulus), modulus));
  }

  State Mod(const long long modulus) const {
    return State(current_ % modulus, next_ % modulus);
  }

  bool operator==(const State& rhs) const { return current_ == rhs.current_ && next_ == rhs.next_; }

 private:
  State(const long long current, const long long next) : current_(current), next_(next) {}

  long long current_;
  long long next_;
};

bool Solve(const State& state, const Transformation& transformation, const long long remainder, const long long modulus_target, long long modulus_current, long long* solution) {
  if (modulus_current == modulus_target) {
    *solution = 0;
    return true;
  }
  const long long divisor = (modulus_target / modulus_current) % 2 ? 5 : 2;
  modulus_current *= divisor;

  State current = state;
  const State state_mod = current.Mod(modulus_current);
  int period = 0;
  while(true) {
     ++period;
     current = current.Apply(transformation, modulus_target);
     if (current.Mod(modulus_current) == state_mod) break;
  }

  const long long remainder_mod = remainder % modulus_current;
  const Transformation transformation_power = transformation.Power(period, modulus_target);
  current = state;
  for (int i = 0; i < period; ++i) {
    if (current.current() % modulus_current == remainder_mod && Solve(current, transformation_power, remainder, modulus_target, modulus_current, solution)) {
      *solution *= period;
      *solution += i;
      return true;
    }
    current = current.Apply(transformation, modulus_target);
  }
  return false;
}

bool Solve(const long long remainder, const long long modulus, long long* solution) {
  return Solve(State(), Transformation(), remainder, modulus, 1, solution);
}

long long Power(const long long a, long long b) {
  long long ret = 1;
  while (b--) ret *= a;
  return ret;
}

int main() {
  char c[kMaxLength + 1];
  scanf("%s", c);
  long long solution;
  if (Solve(atoll(c), Power(10, strlen(c)), &solution)) {
    printf("%lld\n", kPisano + solution);
  } else {
    printf("NIE\n");
  }
  return 0;
}