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
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int MAX_DIGITS = 18;
const long long MODULO = 1000000000000000000LL; // 10 ^ MAX_DIGITS
const int DIGITS_FIB[MAX_DIGITS] = {
    0, 7, 12, 17, 21, 26, 31, 36, 40, 45, 50, 55, 60, 64, 69, 74, 79, 84,
};

long long addMod(long long a, long long b) {
    a %= MODULO;
    b %= MODULO;
    long long result = a - MODULO + b;
    return result < 0? result + MODULO : result;
}

long long multMod(long long a, long long b) {
    a %= MODULO;
    b %= MODULO;
    if(a < b) {
        swap(a, b);
    }

    long long result = 0;
    while(a != 0) {
        if(a & 1) {
            result = addMod(result, b);
        }
        a >>= 1;
        b = addMod(b, b);
    }

    return result;
}

int bitLength(long long n) {
    int result = 0;
    while(n > 0) {
        ++result;
        n /= 2;
    }
    return result;
}

long long fibonacci(long long n) {
    long long f0 = 0, f1 = 1;
    for(int i = bitLength(n) - 1; i >= 0; --i) {
        long long f2 = multMod(f0, addMod(MODULO - f0, 2 * f1));
        long long f3 = addMod(multMod(f0, f0), multMod(f1, f1));
        f0 = f2;
        f1 = f3;

        if((n >> i) & 1 == 1) {
            f2 = addMod(f0, f1);
            f0 = f1;
            f1 = f2;
        }
    }

    return f0;
}

int main() {
    string suffix;
    cin >> suffix;

    long long periods[MAX_DIGITS + 1];
    periods[0] = 1;
    periods[1] = 60;
    periods[2] = 300;
    periods[3] = 1500;
    for(int i = 4; i <= MAX_DIGITS; ++i) {
        periods[i] = periods[i - 1] * 10;
    }

    vector<long long> candidates;
    candidates.push_back(0);
    long long last = 0, power = 1;
    for(int i = 0; i < suffix.length(); ++i) {
        last = power * (suffix[suffix.length() - i - 1] - '0') + last;
        power *= 10;
        vector<long long> newCandidates;
        for(vector<long long>::iterator it = candidates.begin(); it != candidates.end(); ++it) {
            for(long long j = *it; j < periods[i + 1]; j += periods[i]) {
                if(fibonacci(j) % power == last) {
                    newCandidates.push_back(j);
                }
            }
        }
        newCandidates.swap(candidates);
    }

    for(vector<long long>::iterator it = candidates.begin(); it != candidates.end(); ++it) {
        if(*it >= DIGITS_FIB[suffix.length() - 1]) {
            cout << *it << endl;
            return 0;
        }
    }
    cout << "NIE" << endl;

    return 0;
}