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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

typedef unsigned long long ull;

ull multiplicate(ull a, ull b, ull modulo);

struct matrix {
  ull m[2][2];
  
  matrix(ull b1, ull b2, ull b3, ull b4) {
    m[0][0] = b1;
    m[0][1] = b2;
    m[1][0] = b3;
    m[1][1] = b4;
  }
      
  matrix mult(matrix const& A, const ull modulo) const {
    ull b[2][2] = {{0, 0}, {0, 0}};
    for(int i=0; i < 2; ++i)
      for(int j=0; j < 2; ++j)
        for(int k=0; k < 2; ++k) {
      b[i][j] = ((b[i][j] + multiplicate(m[i][k], A.m[k][j], modulo)) % modulo);
    }
    return matrix(b[0][0], b[0][1], b[1][0], b[1][1]);
  }
};


ull multiplicate(ull a, ull b, ull modulo) {
  if (a == 0 || b == 0 || ((64 - __builtin_clzll(a)) + (64 - __builtin_clzll(b))) <= 64) {
    return (a*b) % modulo;
  }
  ull result = 0;
  while (b) {
    if(b&1) {
      result = ((result + a) % modulo);
    }
    b /= 2;
    a = ((a + a) % modulo);
  }
  return result;
}

unsigned long long mods[19];

void fill_mods() {
  mods[0] = 1;
  mods[1] = 60;
  mods[2] = 300;
  mods[3] = 1500;
  FOR(i, 4, 19) {
    mods[i] = mods[i - 1] * 10;
  }
}

matrix power(matrix const& A, unsigned long long k, ull modulo) {
  matrix result(1, 0, 0, 1);
  matrix powe = A;
  while (k != 0) {
    if (k&1) {
      result = result.mult(powe, modulo);
    }
    k /= 2;
    powe = powe.mult(powe, modulo);
  }
  return result;
}

unsigned long long mod_fib(unsigned long long k, unsigned long long modulo) {
  matrix A(0, 1, 1, 1);
  matrix B = power(A, k, modulo);
  return B.m[0][1];
}

ull get_ull(char * raw_ull) {
  return std::stoull (string(raw_ull));
}

char c[19];
int len;
vector<unsigned long long> remiders;
int main() {
  fill_mods();
  scanf("%s", c);
  len = strlen(c);
  remiders.push_back(0);
  int lvl = 0;
  unsigned long long ten = 1;
  while (lvl != len) {
    unsigned long long target = get_ull(c + (len - 1 - lvl));
    vector<unsigned long long> new_remiders;
    ten *= 10;
    for (unsigned long long remider : remiders) {
      for (unsigned long long scale = 0; scale < (mods[lvl + 1] / mods[lvl]); ++scale) {
        unsigned long long possible_remider = remider + mods[lvl] * scale;
        if (mod_fib(possible_remider, ten) == target) {
          new_remiders.push_back(possible_remider);
        }
      }
    }
    lvl++;
    remiders.swap(new_remiders);
  }
  if (remiders.size()) {
    printf("%llu\n", remiders[0]);
  } else {
    printf("NIE\n");
  }
  return 0;
}