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
/*
Zadanie: FIB Fibonacci [A]
Potyczki Algorytmiczne 2015, runda 2. Dostępna pamięć: 64MB
*/

/*
The Pisano periods when n is a power of 10 are 60, 300, 1500, 15000, 150000, ... (sequence A096363 in OEIS).
*/

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>

using namespace std;

#ifdef DEBPRINT
  #define PR(x) cout << #x ": " << x << "\n"; 
  #define P(A) cout << #A << ": " << (A) << " ";
#else
	#define PR(x) ;
	#define P(x) ;
#endif

#define FORi(n) for(int i = 0; i < n; ++ i)
#define FOR(x,n) for(int x = 0; x < n; ++x)

typedef unsigned long long ll;

const int Nmin[]={1,7,12,17,21,26,31,36,40,45,50,55,60,64,69,74,79,84};
const ll M = 1000000000000000000ULL;

inline ll mm(ll a,ll b)
{
	const ll x=1000000000ULL;
	ll u,v;
	v=(a%x)*(b%x);
	return ((a/x)*(b/x)%x+v/x)%x*x+v%x;
}

inline void fibmul(ll* f, ll* g)
{
  ll tmp ;
  tmp  = (mm(f[0],g[0]) + mm(f[1],g[1]))%M;
  f[1] = (mm(f[0],g[1]) + mm(f[1],(g[0] + g[1])%M))%M;
  f[0] = tmp;
}

ll fibonacci(ll n)
{
  ll f[] = { 1ULL, 0ULL };
  ll g[] = { 0ULL, 1ULL };

  while (n > 0ULL)
  {
    if (n & 1ULL) // n odd
    {
      fibmul(f, g);
      --n;
    }
    else
    {
      fibmul(g, g);
      n >>= 1;
    }
  }

  return f[1];
}

char S[20];
int L;
ll N;
 
ll test(ll nr, int cnr, ll d)
{
	ll period, step, F,NR;
	int C,c;
//P("T");P(cnr);P(nr);PR(d);
	switch(cnr)
	{
		case 1: step=1ULL; 	period=60ULL; break;
		case 2: step=60ULL; 	period=300ULL; break;
		case 3: step=300ULL; period=1500ULL; break;
		default:
			{
				step=1500ULL;
				for(int i=4; i<cnr; i++) step*=10ULL;
				period=step*10ULL;
			}
			break;
	}
	period*=2;
//P(step);PR(period);	
//	step=step>>1;
	C=S[L-cnr]-'0';
	for(int i=0; i<=period/step; i++)
	{
		if(Nmin[cnr]<=nr)
		{
			F=fibonacci(nr);
			c=F/d%10ULL;
			if(c==C)
			{
P(S);P(L);P(cnr);P(d);P(C);P(c);P(nr);PR(F);
				if(cnr==L) return nr;
				NR=test(nr,cnr+1,d*10);
//PR(NR);
				if(NR) return NR;
			}
		}
		else
			i--;
		
		if(nr>=18446744073709551615ULL-step) break;
		nr+=step;
	}
	
	
	return 0ULL;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);

//do{
	cin >>S;
	N=atoll(S);
	L=strlen(S);
	ll R=test(1,1,1ULL);
	if (R)
//
		cout <<R;
//cout <<"TAK";
	else
		cout <<"NIE";
	cout<<endl;	
}