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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <iostream>
#include <queue>
using namespace std;
const unsigned long long int million = 1000000000;
class FibNumber{
public:
	FibNumber() {
		a = 1;
		b = 1;
		c = 1;
		d = 0;
		num = 1;
		numHigh = 0;
	}
	FibNumber operator*(FibNumber& n2) {
		return FibNumber(mult(a,n2.a) + mult(b,n2.c), mult(a,n2.b) + mult(b,n2.d)
			, mult(c,n2.a) + mult(d,n2.c), mult(c,n2.b) + mult(d,n2.d),num,n2.num,numHigh,n2.numHigh);
	}
	unsigned long long int getValue() {
		return a;
	}
	unsigned long long int lastValue() {
		return b;
	}
	void printNum() {
		unsigned long long int outNum = num + 1;
		unsigned long long int outNumHigh = numHigh;
		if (outNum >= 1000000000000000000){
			outNum -= 1000000000000000000;
			outNumHigh += 1;
		}
		if (outNumHigh != 0){
			cout << outNumHigh;
		}
		cout << outNum;
	}
	unsigned long long int getNum() {
		return num;
	}
private:
	FibNumber(unsigned long long int a, unsigned long long int b
		, unsigned long long int c, unsigned long long int d
		, unsigned long long int num, unsigned long long int num2,
		unsigned long long int numHigh1, unsigned long long int numHigh2) {
		this->a = a;
		this->b = b;
		this->c = c;
		this->d = d;
		this->num = num + num2;
		this->numHigh = numHigh1 + numHigh2;
		while (num >= 1000000000000000000){
			num -= 1000000000000000000;
			numHigh += 1;
		}
	}
	
	unsigned long long int mult(unsigned long long int a, unsigned long long int b) {
		unsigned long long int aLow = a % million;
		unsigned long long int bLow = b % million;
		unsigned long long int aHigh = (a - a % million) / million;
		unsigned long long int bHigh = (b - b % million) / million;

		unsigned long long int lowPart = aLow*bLow;
		unsigned long long int highPart1 = (aLow*bHigh) % million;
		unsigned long long int highPart2 = (aHigh*bLow) % million;
		unsigned long long int result = ((((highPart1 + highPart2 + ((lowPart - lowPart % million)/ million)) % million) * million)
			+ (lowPart % million));
		return result % 1000000000000000000;
	}
	unsigned long long int a, b, c, d;
	unsigned long long int num;
	unsigned long long int numHigh;
};

int main() {

	char c;
	unsigned long long int value = 0;
	int digits = 0;
	while (cin >> c){
		value *= 10;
		value += c - '0';
		++digits;
	}

	//TODO obsluzyc 0,1 ... itp.
	queue<FibNumber>* currentQ = new queue<FibNumber>();
	queue<FibNumber>* nextQ = new queue<FibNumber>();

	currentQ->push(FibNumber());

	FibNumber multiplicator;
	FibNumber accumulator;

	unsigned long long int inputNumber = 0;

	unsigned long long int digitValue = 10;

	for (int digit = 1; digit <= digits && !currentQ->empty(); ++digit,digitValue *= 10ULL){

		multiplicator = accumulator;
		accumulator = FibNumber();
		//cout << " nowy mnoznik : " << multiplicator.getValue() << " numer : " << multiplicator.getNum() << endl;
		//cout << " mamy kandydatow : " << currentQ->size() << endl;

		bool foundCycle = false;
		int cycleSize = 0;

		int candidatesC = currentQ->size();
		int counter = candidatesC+1;

		int currentDigitGoal = currentQ->front().getValue() % (digitValue);
		int lastDigitGoal = currentQ->front().lastValue() % (digitValue);
		//std::cout << "zaczynamy od " << lastDigitGoal << " " << currentDigitGoal << endl;

		inputNumber += (value % digitValue);
		value -= (value % digitValue);

		//std::cout << " szukamy : " << inputNumber << endl;

		accumulator = multiplicator;

		bool once = true;

		while (!foundCycle){
			++cycleSize;
			//std::cout << currentQ->front().getValue() << " numer : " << currentQ->front().getNum();
			FibNumber n = currentQ->front() * multiplicator;
			//std::cout << " --> " << n.getValue() << " numer : " << n.getNum() << endl;
			currentQ->pop();
			int currentDigit = n.getValue() % digitValue;
			int lastDigit = n.lastValue() % digitValue;
			if (currentDigit == inputNumber){
				nextQ->push(n);
				//std::cout << " found : " << n.getValue() << " numer : " << n.getNum() << endl;
			}
			currentQ->push(n);
			if (currentDigit == currentDigitGoal && lastDigit == lastDigitGoal){
				//std::cout << " zakonczylismy na " << n.lastValue() << " " << n.getValue() << " numer : " << n.getNum() << endl;
				if (once) once = false;
				else foundCycle = true;
			}
			if (!foundCycle && --counter == 0){
				accumulator = accumulator*multiplicator;
				counter = currentQ->size();
			}
		}

		/*std::cout << " found " << nextQ->size() << endl;
		while (!nextQ->empty()){
			FibNumber num = nextQ->front();
			std::cout << " >> " << nextQ->front().getValue() << endl;
			nextQ->pop();
			std::cout << " >> > " << (num * accumulator).getValue() << endl;
		}*/

		queue<FibNumber>* tempPtr = nextQ;
		nextQ = currentQ;
		currentQ = tempPtr;
		while (!nextQ->empty()) nextQ->pop();

	}

	if (!currentQ->empty()){
		currentQ->front().printNum();
		cout << endl;
	} else {
		cout << "NIE\n";
	}

}