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
#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef long long LL;
const int ten9 = 1000000000;
const LL ten18 = LL(ten9) * LL(ten9);

void ReadInput(int &n, LL &rem) {
  string text;
  cin >> text;
  n = text.size();
  rem = 0;
  for (char c : text) {
    rem = 10*rem + (c-'0');
  }
}

vector<LL> POW10;

class Mod {
 public:
  Mod():val(0) {}
  explicit Mod(LL x):val(x) {}
  Mod operator+(const Mod &b) const {
    return Mod((get() + b.get()) % ten18);
  }
  Mod operator*(const Mod &b) const {
    LL res = LL(val % ten9) * LL(b.val % ten9);
    LL resHi = LL(val % ten9) * LL(b.val / ten9) +
               LL(val / ten9) * LL(b.val % ten9);
    res += (resHi % ten9) * LL(ten9);
    res %= ten18;
    return Mod(res);
  }
  LL get() const { return val; }
 private:
  LL val;
};

struct FibPair {
  LL k;
  Mod fibK;
  Mod fibKm1;
};

inline FibPair operator+(const FibPair &a, const FibPair &b) {
  FibPair res;
  res.k = a.k + b.k;
  res.fibK = a.fibK * (b.fibK + b.fibKm1) + a.fibKm1 * b.fibK;
  res.fibKm1 = a.fibK * b.fibK + a.fibKm1 * b.fibKm1;
  return res;
}

LL Solve(int n, LL rem) {
  POW10.resize(n+1);
  POW10[0] = 1;
  for(int i=1;i<=n;++i) POW10[i] = POW10[i-1] * 10;

  int digs = 0;
  vector<FibPair> f_good;
  FibPair f_len;
  {
    FibPair f0;
    f0.k = 0;
    f0.fibK = Mod(0);
    f0.fibKm1 = Mod(1);
    f_good.push_back(f0);
  }
  {
    FibPair f1;
    f1.k = 1;
    f1.fibK = Mod(1);
    f1.fibKm1 = Mod(0);
    f_len = f1;
  }

  vector<FibPair> f_good2;
  while (digs < n) {
    ++digs;
    LL remDigs = rem % POW10[digs];
    f_good2.clear();
    FibPair f_len2 = f_len;
    for(;;) {
      for(const auto &fp : f_good) {
        if (fp.fibK.get() % POW10[digs] == remDigs) {
          f_good2.push_back(fp);
        }
      }
      if(f_len2.fibK.get() % POW10[digs] == 0 &&
         f_len2.fibKm1.get() % POW10[digs] == 1) {
        break;
      }
      f_len2 = f_len2 + f_len;
      for(auto &fp : f_good) {
        fp = fp + f_len;
      }
    }
    f_len = f_len2;
    f_good.swap(f_good2);
  }
  if(f_good.empty()) return -1;
  return f_good[0].k + f_len.k;
}

int main() {
  int n;
  LL rem;
  ReadInput(n, rem);
  LL res = Solve(n, rem);
  if (res==-1) cout << "NIE\n";
  else cout << res << "\n";
}