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

const long long modulo = (long long)1e18;

long long mulmod(long long a, long long b) {
  const long long M = modulo;
  const int MM = (int)1e9;
  int ah = a/MM;
  int al = a%MM;
  int bh = b/MM;
  int bl = b%MM;
  long long rl = ((long long)al)*bl;
  long long rh = (rl/MM)+((long long)ah)*bl+((long long)al)*bh;
  rl %= MM;
  rh %= M/MM;
  return rh*MM+rl;
}

std::pair<long long, long long> fibbonaci(long long n) {
  if (n == 1)
    return std::make_pair(1, 1);
  std::pair<long long, long long> r = fibbonaci(n/2);
  long long a = r.first;
  long long b = r.second;
  long long t = b * 2 - a;
  if (t < 0)
    t += modulo;
  long long c = mulmod(a, t);
  long long d = (mulmod(a, a)+mulmod(b, b))%modulo;
  if (n&1)
    return std::make_pair(d, (c+d)%modulo);
  return std::make_pair(c, d);
}

char digits[20];
int len;

constexpr long long fig[] = {
  1, 10, 100, (long long)1e3, (long long)1e4, (long long)1e5, (long long)1e6, (long long)1e7, (long long)1e8, (long long)1e9,
  (long long)1e10, (long long)1e11, (long long)1e12, (long long)1e13, (long long)1e14, (long long)1e15, (long long)1e16, (long long)1e17, (long long)1e18
};

constexpr long long cycl[] = {
  60, 300, (long long)15e2, (long long)15e3, (long long)15e4, (long long)15e5,
  (long long)15e6, (long long)15e7, (long long)15e8, (long long)15e9, (long long)15e10, (long long)15e11,
  (long long)15e12, (long long)15e13, (long long)15e14, (long long)15e15, (long long)15e16, (long long)15e17
};

std::pair<long long, long long> cycl_fibs[18];

const int PRE_C = 5;
const int MAX_PRE = cycl[PRE_C-1];
const int MAX_PRE_FIG = fig[PRE_C];
struct list {
  int value;
  list* next;
};
list elems[MAX_PRE];
list* heads[MAX_PRE_FIG];

void precomp() {
  long long a = 0;
  heads[0] = &elems[0];
  long long b = 1;
  for (int i = 1; i < MAX_PRE; ++i) {
    int c = b;
    b = (a+b)%MAX_PRE_FIG;
    a = c;
    elems[i].value = i;
    elems[i].next = heads[a];
    heads[a] = &elems[i];
  }
  
  for (int i = 0; i < 18; ++i) {
    cycl_fibs[i] = fibbonaci(cycl[i]-1);
  }
}

std::pair<long long, long long> advance(std::pair<long long, long long> a, std::pair<long long, long long> b) {
  long long c = mulmod(a.first, b.first)+mulmod(a.second, b.second);
  long long d = mulmod(a.second, (b.first+b.second)%modulo)+mulmod(a.first, b.second);
  return std::make_pair(c%modulo, d%modulo);
}

long long backtrack(std::pair<long long, long long> val, int cur) {
  if (cur == len)
    return 0;
  for (int i = 0; i < 10; ++i) {
    if ((digits[len-cur-1]-'0') == (val.first/fig[cur])%10) {
      long long r = backtrack(val, cur+1);
      if (r >= 0)
	return i*cycl[cur-1]+r;
    }
    val = advance(val, cycl_fibs[cur-1]);
  }
  return -1;
}

int main() {
  precomp();
  scanf("%s", digits);
  len = strlen(digits);
  if (len <= PRE_C) {
    long long postfix;
    sscanf(digits, "%lld", &postfix);
    for (; postfix < MAX_PRE_FIG; postfix += fig[len]) {
      if (heads[postfix]) {
	printf("%lld\n", cycl[len-1]+heads[postfix]->value);
	return 0;
      }
    }
  } else {
    long long postfix;
    sscanf(&digits[len-PRE_C], "%lld", &postfix);
    for (list* elem = heads[postfix]; elem; elem = elem->next) {
      long long r = backtrack(fibbonaci(elem->value), PRE_C);
      if (r >= 0) {
	printf("%lld\n", cycl[len-1]+elem->value+r);
	return 0;
      }
    }
  }
  printf("NIE\n");
}