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
#include <iostream>
#include <vector>
using namespace std;

struct DuzaLiczba {
	long long l[2];
	const static long long mod = 1000000000;
	
	DuzaLiczba(): DuzaLiczba(0) {}
	
	DuzaLiczba(long long liczba) {
		l[0] = liczba / mod;
		l[1] = liczba % mod;
	}
	
	DuzaLiczba operator*(const DuzaLiczba& l2) const {
		DuzaLiczba d = 0;
		d.l[0] = l[0] * l2.l[1] + l[1] * l2.l[0];
		d.l[1] = l[1] * l2.l[1];
		d.l[0] = (d.l[0] + d.l[1] / mod) % mod;
		d.l[1] = d.l[1] % mod;
		return d;
	}
	
	DuzaLiczba operator+(const DuzaLiczba& l2) const {
		DuzaLiczba d = 0;
		d.l[0] = l[0] + l2.l[0];
		d.l[1] = l[1] + l2.l[1];
		d.l[0] = (d.l[0] + d.l[1] / mod) % mod;
		d.l[1] = d.l[1] % mod;
		return d;
	}
	
	long long operator%(long long l2) const {
		return (l[0] * mod + l[1]) % l2;
	}
	
	friend ostream& operator<<(ostream& os, const DuzaLiczba& l) {
		return os << l.l[0] * l.mod + l.l[1];
	} 
};

struct S {
	DuzaLiczba t[2][2];

	S(): S(1, 0, 0, 1) {}

	S(long long a, long long b, long long c, long long d) :t({{a,b},{c,d}}) {
	}
	
	S operator*(const S& s2) {
		S s;
		s.t[0][0] = t[0][0] * s2.t[0][0] + t[0][1] * s2.t[1][0];
		s.t[0][1] = t[0][0] * s2.t[0][1] + t[0][1] * s2.t[1][1];
		s.t[1][0] = t[1][0] * s2.t[0][0] + t[1][1] * s2.t[1][0];
		s.t[1][1] = t[1][0] * s2.t[0][1] + t[1][1] * s2.t[1][1];
		return s;
	}
};

S pot[100];
long long k[20];
S tab[20];

vector <pair <long long, S> > v[20];

int main() {
	pot[1] = {1, 1, 1, 0};
	for(int i = 2; i <= 60; i ++) {
		pot[i] = pot[i - 1] * pot[i - 1];
	}
	k[0] = 1;
	k[1] = 60;
	k[2] = 300;
	k[3] = 1500;
	for(int i = 4; i <= 18; i ++) {
		k[i] = k[i - 1] * 10;
	}
	for(int i = 0; i <= 18; i ++) {
		long long m = k[i];
		int x = 1;
		tab[i] = pot[0];
		while(m) {
			if(m % 2) {
				tab[i] = tab[i] * pot[x]; 
			}
			x ++;
			m /= 2;
		}
	}
	string s;
	cin >> s;
	long long mod = 1;
	long long c = 0;
	v[0].emplace_back(0, pot[0]);
	for(int i = 0; i < s.size(); i ++) {
		c += (s[s.size() - i - 1] - '0') * mod;
		mod *= 10;
		for(int j = 0; j < v[i].size(); j ++) {
			S t = v[i][j].second;
			for(long long nr = v[i][j].first; nr < k[i + 1]; nr += k[i]) {
				if(t.t[0][1] % mod == c) {
					v[i + 1].emplace_back(nr, t);
				}
				t = t * tab[i]; 
			}
		}
	}
	if(v[s.size()].size()) {
		cout << v[s.size()][0].first + k[s.size()] << endl;
	}
	else {
		cout << "NIE" << endl;
	}
	return 0;
}