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

using namespace std;

struct matr_2x2 {
	long long a11, a12, a21, a22, modulo;
	matr_2x2(long long a11_, long long a12_, long long a21_, long long a22_, long long m_)
		: a11(a11_), a12(a12_), a21(a21_), a22(a22_), modulo(m_)
	{ };
};

long long mul_by_modulo(long long a, long long b, long long modulo)
{
	long long res = 0LL;
	while(b) {
		if(b & 1LL) {
			res += a;
			res %= modulo;
		}
		a <<= 1;
		a %= modulo;
		b >>= 1;
	}
	return res;
}

matr_2x2 mul(const matr_2x2 &A, const matr_2x2 &B)
{
#ifdef _DEBUG
	if(A.modulo != B.modulo)
		_DEBUG_ERROR("A.modulo != B.modulo");
#endif
	return matr_2x2(
		(mul_by_modulo(A.a11, B.a11, A.modulo) + mul_by_modulo(A.a12, B.a21, A.modulo)) % A.modulo,
		(mul_by_modulo(A.a11, B.a12, A.modulo) + mul_by_modulo(A.a12, B.a22, A.modulo)) % A.modulo,
		(mul_by_modulo(A.a21, B.a11, A.modulo) + mul_by_modulo(A.a22, B.a21, A.modulo)) % A.modulo,
		(mul_by_modulo(A.a21, B.a12, A.modulo) + mul_by_modulo(A.a22, B.a22, A.modulo)) % A.modulo,
		A.modulo
	);
};

matr_2x2 pow(matr_2x2 A, long long n) // A should be passed by copy
{
	matr_2x2 res = matr_2x2(1LL, 0LL, 0LL, 1LL, A.modulo); // E, i.e. unitary matrix
	while(n) {
		if(n & 1LL) {
			res = mul(res, A);
		}
		A = mul(A, A);
		n >>= 1;
	}
	return res;
}


int main(int argc, char* argv[])
{
	string need_suffix;
	cin >> need_suffix;
	string cutted_suffix = need_suffix;
	if(cutted_suffix.size() > 5) {
		cutted_suffix.erase(0, cutted_suffix.size() - 5);
	}
	vector<vector<int> > reached_at(100000);

	long long modulo = 10;
	for(size_t i=1; i<cutted_suffix.size(); i++)
		modulo *= 10;
	int fib_0 = 0;
	int fib_1 = 1;
	int fib_2;
	int idx = 1;
	matr_2x2 FIB_MATRIX(1LL, 1LL, 1LL, 0LL, modulo);
	do {
		fib_2 = (fib_0 + fib_1) % ((int)modulo);
		fib_0 = fib_1;
		fib_1 = fib_2;
		idx++;
#ifdef _DEBUG
		long long curr_fib_via_matrix = pow(FIB_MATRIX, idx).a21;
		if(fib_1 != curr_fib_via_matrix)
			_DEBUG_ERROR("fib_1 != curr_fib_via_matrix");
#endif
		reached_at[fib_1].push_back(idx);
	}
	while(!(fib_0==0 && fib_1==1));
	long long suff_as_num, suff_as_num_cutted;
	stringstream istr(need_suffix);
	istr >> suff_as_num;
	suff_as_num_cutted = suff_as_num % modulo;
	if(reached_at[suff_as_num_cutted].empty()) {
		cout << "NIE\n";
	} else if(need_suffix.size() <= 5) {
		cout << reached_at[suff_as_num][0] + (idx-1) << endl;
	} else { // need_suffix.size() >= 6
		vector<long long> pos_of_needed_suffix_prev(reached_at[suff_as_num_cutted].size());
		for(size_t i = 0; i < pos_of_needed_suffix_prev.size(); i++)
			pos_of_needed_suffix_prev[i] = (long long)reached_at[suff_as_num_cutted][i];
		long long cycle_length = reached_at.size() + (reached_at.size() /2);
		for(size_t suff_len = 6; suff_len<=need_suffix.size(); suff_len++) {
			modulo *= 10LL;
			suff_as_num_cutted = suff_as_num % modulo;
			vector<long long> pos_of_needed_suffix_next;
			matr_2x2 FIB_MATRIX(1LL, 1LL, 1LL, 0LL, modulo);
			for(vector<long long>::iterator v = pos_of_needed_suffix_prev.begin(); v != pos_of_needed_suffix_prev.end(); v++) {
				for(long long num_cycles = 0LL; num_cycles < 10LL; num_cycles+=1LL) {
					long long found_fib = pow(FIB_MATRIX, *v + num_cycles*cycle_length).a21;
					if(found_fib == suff_as_num_cutted)
						pos_of_needed_suffix_next.push_back(*v + num_cycles*cycle_length);
				}
			}
			pos_of_needed_suffix_prev = pos_of_needed_suffix_next;
			cycle_length *= 10LL;
		}
		if(pos_of_needed_suffix_prev.empty())
			cout << "NIE\n";
		else
			cout << pos_of_needed_suffix_prev[0] + cycle_length << endl;
	}
	return 0;
}