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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef unsigned long long int LL;
char s[30];
long long int a[2][2], b[2][2], p[2][2], mod;
struct wp {
	vector <LL> v;
	LL mn, mod;
}t[30];
vector <LL> v; 
void zeruj ()
	{
	a[0][0]=a[1][1]=1;
	a[0][1]=a[1][0]=0;
	b[0][0]=b[0][1]=b[1][0]=1;
	b[1][1]=0;
	}
void mno(long long int c[2][2], long long int d[2][2])
	{
	p[0][0]=p[0][1]=p[1][0]=p[1][1]=0;
	for (int i=0; i<=1; i++)
		for (int j=0; j<=1; j++)
			for (int k=0; k<=1; k++)
				p[i][j]=(p[i][j]+(c[i][k]*d[k][j])%mod)%mod;
	for (int i=0; i<=1; i++)
		for (int j=0; j<=1; j++)
			c[i][j]=p[i][j];
	}
LL fibo (LL x)
	{
	zeruj();
	x+=1;
	while (x>0)
		{
		if (x%2) mno(a, b);
		mno(b, b);
		x/=2;
		}
	return a[1][1];
	}
LL dlugosc ()
	{
	int i=1;
	for (; s[i]!=0; i++);
	return i;
	}
int dl_licz (LL a)
	{
	int odp=0;
	printf ("{%lld ", a);
	if (a==0LL) return 1; 
	while (a>0)
		{
		odp++;
		a/=10LL;
		}
	printf ("%d} ", odp);
	return odp;
	}
int main ()
{
t[0].mod=1;
t[1].mn=60;t[2].mn=300;t[3].mn=1500;
for (int i=4; i<=19; i++) t[i].mn=t[i-1].mn*10LL;
for (int i=1; i<=19; i++) t[i].mod=t[i-1].mod*10LL;
LL licz=0, a=0, b=1;
scanf ("%s", s+1);
LL dl=dlugosc();
for (int i=1; s[i]!=0; i++)
	{
	licz*=10;
	licz+=(LL)(s[i]-48);
	}
dl--; mod=pow(10LL, dl);
//printf ("%lld %lld %lld\n", dl, licz, mod);
if (licz%10LL==0) v.push_back(0);
if (licz%10LL==1) v.push_back(1);
for (int i=2; i<60; i++)
	{
	a=(a+b)%mod;
	swap (a, b);
	if (licz%t[1].mod==b%t[1].mod)
		t[1].v.push_back(i);
	}
for (int i=2; i<=dl; i++)
	{
	for (vector <LL>::iterator it=t[i-1].v.begin(); it!=t[i-1].v.end(); it++)
		{
		for (LL j=0; j*t[i-1].mn+(*it)<t[i].mn; j++)
			{
			if (fibo(j*t[i-1].mn+(*it))%t[i].mod==licz%t[i].mod)
				t[i].v.push_back(j*t[i-1].mn+(*it));
			}
		}
	}
/*for (int i=1; i<=dl; i++)
	{
	printf ("%d : ", i);
	for (vector <LL>::iterator it=t[i].v.begin(); it!=t[i].v.end(); it++)
		printf ("%lld ", *it);
	printf ("\n");
	}*/
if (t[dl].v.size()==0) printf ("NIE");
else
	{
	printf ("%lld", *t[dl].v.begin()+t[dl].mn);
	}
return 0;
}