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

constexpr unsigned long long power(unsigned long long a, unsigned b) {
    return b == 0 ? 1 : a * power(a, b-1);
}

struct Integer {
    static unsigned long long const MOD = power(10, 9);
    unsigned long long hi, lo;
    constexpr Integer(unsigned long long num): hi(num / MOD), lo(num % MOD) {}

    Integer& fix() {
        hi += lo / MOD;
        lo %= MOD;
        hi %= MOD;

        return *this;
    }

    Integer& operator -= (Integer const& rhs) {
        hi += 2*MOD - rhs.hi - 1;
        lo += MOD - rhs.lo;

        return this->fix();
    }

    Integer& operator += (Integer const& rhs) {
        hi += rhs.hi;
        lo += rhs.lo;
        fix();
        return this->fix();
    }

    Integer& operator *= (Integer const& rhs) {
        hi = hi * rhs.lo + lo * rhs.hi;
        lo *= rhs.lo;
        return this->fix();
    }

    explicit operator unsigned long long () const {
        return hi * MOD + lo;
    }
};

Integer const operator + (Integer lhs, Integer const& rhs) {
    return lhs += rhs;
}

Integer const operator * (Integer lhs, Integer const& rhs) {
    return lhs *= rhs;
}

Integer const operator - (Integer lhs, Integer const& rhs) {
    return lhs -= rhs;
}

std::pair<Integer, Integer> const fib_rec(unsigned long long term) {
    if(term == 0) return {0, 1};
    if(term % 2 == 1){
        auto pair = fib_rec(term - 1);
        return {pair.second, pair.first + pair.second};
    }
    auto pair = fib_rec(term / 2);
    return {pair.first * (2 * pair.second - pair.first), pair.first * pair.first + pair.second * pair.second};
}

unsigned long long fibonacci(unsigned long long term) {
    auto res = static_cast<unsigned long long>(fib_rec(term).first);
    return res;
}

std::vector<unsigned long long> const make_cycles() {
    std::vector<unsigned long long> result {1, 60, 300, 1500};
    for(unsigned i = 4; i <= 18; i++) {
        result.push_back(result.back() * 10);
    }

    return result;
}

std::vector<unsigned long long> const make_powers() {
    std::vector<unsigned long long> result {1};
    for(unsigned i = 1; i <= 18; i++) {
        result.push_back(result.back() * 10);
    }

    return result;
}

const std::vector<unsigned long long> cycles = make_cycles();
const std::vector<unsigned long long> powers = make_powers();

bool backtrack(unsigned digit, std::string const& suf, unsigned long long & result) {
    if(digit >= suf.size()) return true;

    unsigned long long target = std::stoll(suf.substr(suf.length() - digit - 1));
    unsigned long long modulus = powers[digit+1];

    unsigned long long prior = cycles[digit];
    unsigned long long now = cycles[digit+1];

    unsigned long long tmp_res = result;

    for(unsigned i = 0; i < now / prior; i++) {
        if(fibonacci(result) % modulus == target && backtrack(digit + 1, suf, result)) return true;
        result += prior;
    }

    result = tmp_res;

    return false;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::string suf;
    std::cin >> suf;
    unsigned long long result = 0;
    if(backtrack(0, suf, result)) {
        std::cout << result + cycles.back() << std::endl;
    } else {
        std::cout << "NIE" << std::endl;
    }
}