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
#include <bits/stdc++.h>

using namespace std;

const int N = 19;

long long cycleLength[N + 5];
long long M;
char input[N];

inline long long add(long long a, long long b) {
    if (a + b >= M) {
        return a + b - M;
    }
    return a + b;
}

long long mul(long long a, long long b) {
    if (b == 0) {
        return 0;
    }
    if (b == 1) {
        return a;
    }
    if (a > b) {
        swap(a, b);
    }
    if (b <= 1e9) {
        return a * b % M;
    }
    
    long long ret = mul(a, b / 2);
    
    return add(add(ret, ret), (b % 2? a: 0));
}

inline void multiply(long long &leftTop, long long &rightTop,
                     long long &leftBottom, long long &rightBottom,
                     long long &leftTopB, long long &rightTopB,
                     long long &leftBottomB, long long &rightBottomB) {
    long long retA = add(mul(leftTop, leftTopB), mul(rightTop, leftBottomB));
    long long retB = add(mul(leftTop, rightTopB), mul(rightTop, rightBottomB));
    long long retC = add(mul(leftBottom, leftTopB), mul(rightBottom, leftBottomB));
    long long retD = add(mul(leftBottom, rightTopB), mul(rightBottom, rightBottomB));
    leftTop = retA;
    rightTop = retB;
    leftBottom = retC;
    rightBottom = retD;
}

long long fastFib(long long n) {
    
    long long leftTop = 1;
    long long rightTop = 1;
    long long leftBottom = 1;
    long long rightBottom = 0;
    
    long long ansLeftTop = 1;
    long long ansRightTop = 0;
    long long ansLeftBottom = 1;
    long long ansRightBottom = 0;
    
    while(n >= 1) {
        if (n % 2 == 1) {
            multiply(ansLeftTop, ansRightTop, ansLeftBottom, ansRightBottom, leftTop, rightTop, leftBottom, rightBottom);
        }
        multiply(leftTop, rightTop, leftBottom, rightBottom, leftTop, rightTop, leftBottom, rightBottom);
        n /= 2;
    }
    
    return ansRightTop;
}


int main() {
    
    cycleLength[0] = 1;
    cycleLength[1] = 60;
    cycleLength[2] = 300;
    cycleLength[3] = 1500;
    for (int i = 4; i < N; i++) {
        cycleLength[i] = cycleLength[i - 1] * 10;
    }
    
    scanf("%s", &input[1]);
    
    int moduloExp = strlen(input + 1);
    long long searchingValue = atoll(input + 1);
    
    vector<long long> goodValues;
    goodValues.push_back(0);
    M = 10;
    
    for (int i = 1; i <= moduloExp; i++) {
        vector<long long> newGoodValues;
        long long searchingValueMod = searchingValue % M;
        
        for (int j = 0; j < goodValues.size(); j++) {
            long long x = goodValues[j];
            
            while (x < cycleLength[i]) {
                if (fastFib(x) == searchingValueMod) {
                    newGoodValues.push_back(x);
                }
                
                x += cycleLength[i - 1];
            }
        }
        
        goodValues = newGoodValues;
        M *= 10;
        sort(goodValues.begin(), goodValues.end());
    }
    
    if (goodValues.size() == 0) {
        printf("NIE\n");
    } else {
        printf("%lld\n", goodValues[0] + 1500000000000000000LL);
    }
    
    return 0;
}