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
#include<bits/stdc++.h>
#define FOR(i,s,e) for(int i=(s);i<=(e);i++)
#define FORD(i,s,e) for(int i=(s);i>=(e);i--)
#define ALL(k) (k).begin(),(k).end()
#define e1 first 
#define e2 second
#define MP make_pair
#define PB push_back
#define EB emplace_back 
using namespace std;
typedef unsigned long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<int,PII> PIP;
typedef pair<PLL,PLL> PPP;
const LL TYS=1000;
const LL MLN=TYS*TYS;
const LL MLD=MLN*TYS;
const int MAXN=150111;
char a[MAXN];
LL MOD;
LL M2=MLD;

LL mnoz(LL a,LL b){
	LL a1=a/M2,a2=a%M2;
	LL b1=b/M2,b2=b%M2;
	LL wynik=(((a2*b2)%MOD)+((a1*b2)%M2)*M2)%MOD+(((a2*b1)%M2)*M2)%MOD;
	return wynik%MOD;
}
PPP mnmac(PPP a,PPP b){
	PPP ans;
	ans.e1.e1=(mnoz(a.e1.e1,b.e1.e1)+mnoz(a.e1.e2,b.e2.e1))%MOD;
	ans.e1.e2=(mnoz(a.e1.e1,b.e1.e2)+mnoz(a.e1.e2,b.e2.e2))%MOD;
	ans.e2.e1=(mnoz(a.e2.e1,b.e1.e1)+mnoz(a.e2.e2,b.e2.e1))%MOD;
	ans.e2.e2=(mnoz(a.e2.e1,b.e1.e2)+mnoz(a.e2.e2,b.e2.e2))%MOD;
	return ans;
}
LL fibon(LL k){
	PPP wyn={{1,0},{0,1}};
	PPP a={{1,1},{1,0}};
	while(k>0){
		if(k%2) wyn=mnmac(wyn,a);
		a=mnmac(a,a);
		k/=2;
	}
	return wyn.e1.e2;
}



LL fib[MAXN];
vector<LL> positions[MAXN];
main(){
	scanf("%s",a);
	LL wyn=0;
	LL dl=1;
	int dlu=0;
	for(int i=0;a[i]>0;i++){
		dl*=10;
		dlu++;
		wyn*=10;
		wyn+=a[i]-'0';
	}
	reverse(a,a+dlu);
	//printf("%d %llu %llu\n",dlu,dl,wyn);
	fib[0]=0;fib[1]=1;
	MOD=min(dl,(LL)1000);
	LL ob=wyn%TYS;
	//printf("%llu %llu\n",MOD,ob);
	int cl=1500;
	if(dlu==1) cl=60;
	if(dlu==2) cl=300;
	FOR(i,2,MAXN){
		fib[i]=(fib[i-1]+fib[i-2])%MOD;
		if(dl<=1000&&wyn==fib[i]) {printf("%d\n",i+cl);return 0;}
		if(ob==fib[i]) positions[3].PB(i);
		if(fib[i]==1&&fib[i-1]==0) break;
	}
	if(dl<=1000){puts("NIE");return 0;}
	LL cycle_len=150;
	FOR(i,3,dlu-1){
		if(positions[i].empty()) {puts("NIE");return 0;}
		/*printf("szukaj %d:: ",i);
		for(auto it:positions[i]) printf("%llu ",it);
		puts("");*/
		
		cycle_len*=10;
		ob+=(a[i]-'0')*MOD;
		MOD*=10;
		//printf("MOD==%llu, cl==%llu,ob==%llu\n",MOD,cycle_len,ob);
		for(auto it:positions[i]){
			//printf("%4llu:: ",it);
			for(LL k=0;k<10;k++){
				LL w1=fibon(it+k*cycle_len);
				//printf("%4lld %4lld;; ",it+k*cycle_len,w1);
				if(w1==ob) positions[i+1].PB(it+k*cycle_len);
			}
			//puts("");
		}
	}
	sort(ALL(positions[dlu]));
	if(positions[dlu].empty()) {puts("NIE");return 0;}
	else printf("%llu\n",positions[dlu][0]+cycle_len);
	//printf("%llu\n",fibon(positions[dlu][0]));
		
	//printf("%llu\n",fibon(655894));
		
}