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
#include <bits/stdc++.h>
using namespace std;

#define fru(j,n) for(int j=0; j<(n); ++j)
#define tr(it,v) for(auto it=(v).begin(); it!=(v).end(); ++it)
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define ALL(G) (G).begin(),(G).end()

typedef long long ll;
typedef double D;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
const int inft = 1000000009;
const int MAXN = 1000006,ZN=18;

ll cycle[ZN+1],mod[ZN+1];

#define MOD mod[ZN]
#define ADD(a,b) {(a)+=(b); if((a)>=MOD)(a)-=MOD;}
ll mnoz(ll a,ll b){
	ll c=0;
	while(b){
		if(b%2)ADD(c,a)
		ADD(a,a)
		b/=2;
	}
	return c; 
}
ll F(ll n){ //F[n]%MOD
	ll W[2][2],M[2][2],T[2][2];
	W[0][0]=W[1][1]=M[0][0]=M[0][1]=M[1][0]=1;
	W[0][1]=W[1][0]=M[1][1]=0;
	while(n){
		if(n%2){
			fru(i,2)fru(j,2){
				T[i][j]=0;
				fru(k,2)
					ADD(T[i][j],mnoz(W[i][k],M[k][j]))	
			}
			fru(i,2)fru(j,2)W[i][j]=T[i][j];
		}
		n/=2;
		fru(i,2)fru(j,2){
			T[i][j]=0;
			fru(k,2)
				ADD(T[i][j],mnoz(M[i][k],M[k][j]))	
		}
		fru(i,2)fru(j,2)M[i][j]=T[i][j];
	}
	return W[1][0];
}
char str[ZN+10];
void solve() {
	mod[0]=1;
	fru(i,ZN+1)if(i)mod[i]=mod[i-1]*10;
	cycle[1]=60;cycle[2]=300;cycle[3]=1500;
	fru(i,ZN+1)if(i>3)cycle[i]=cycle[i-1]*10;
	int n;
	ll liczba=0;
	scanf(" %s",str);
	n=strlen(str);
	fru(i,n)liczba+=mod[n-i-1]*(str[i]-'0');
/*	ll F0=0,F1=1,temp;
//	printf("%lld\n",mod[n]);
	for(ll i=0;i<cycle[n];i++){
		if(i%mod[n]==0)printf("%lld of %lld\n",i,cycle[n]);
		if(F0!=F(i)%mod[n]){printf("%lld -> %lld, rek %lld \n",i,F0,F(i));break;}
		temp=(F0+F1);
		if(temp>=mod[n])temp-=mod[n];
		F0=F1;F1=temp;
	}
	return;*/
	vector<ll> P[2];
	//init last digit
	fru(i,cycle[1])if(F(i)%mod[1]==liczba%mod[1])P[0].pb(i);
//	tr(it,P[0]){printf("%lld ->%lld\n",*it,F(*it));}
	for(int i=2;i<=n;i++){
		tr(it,P[0]){
			for(ll curr=*it;curr<cycle[i];curr+=cycle[i-1]){
					if(F(curr)%mod[i]==liczba%mod[i])P[1].pb(curr);
				}
		}
		swap(P[0],P[1]);
		P[1].clear();
	//	tr(it,P[0]){printf("%lld ->%lld\n",*it,F(*it));}
	//	printf("step %d, size %d\n",i,P[0].size());
	}
	if(P[0].empty()){puts("NIE");return;}
	printf("%lld\n",P[0][0]+cycle[n]);
}

int main() {
	solve();
	return 0;
}