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

struct Fib
{
	unsigned long long int fprev;
	unsigned long long int f;
	unsigned long long int fnext;
};
const unsigned long long int d18=1000000000000000000L;
const unsigned long long int dz9=1000000000;

const Fib jeden={0,1,1};
const Fib id={1,0,1};

const unsigned long long UPP=0xffffffff00000000;
const unsigned long long LOW=0x00000000ffffffff;


inline unsigned long long int mult(unsigned long long int a,unsigned long long int b)
{
	return (((a%dz9)*(b%dz9))%d18+ (((((a%dz9)*(b/dz9)))%dz9)*dz9)%d18 +(((((b%dz9)*(a/dz9)))%dz9)*dz9)%d18)%d18;
}

Fib operator*(Fib a,Fib b)
{
	Fib c;
	c.fprev=(mult(a.fprev,b.fprev)+mult(a.f,b.f))%d18;

	c.f =(mult(a.fprev,b.f)+mult(a.f,b.fnext))%d18;
	c.fnext =(c.fprev+c.f)%d18;
	return c;
}
Fib operator^(Fib a,unsigned long long int b)
{
	if(b==0)return id;
	Fib x=id;
	while(b>0)
	{
		if(b&1)x=x*a;
		a=a*a;
		b=b>>1;
	}
	return x;
}

unsigned long long int pow(long long int a, int b)
{	
	if(b==0)return 1;
	unsigned long long int x=1;
	while(b>0)
	{
		if(b&1)x=x*a;
		a=a*a;
		b=b>>1;
	}
	return x;
}

list<Fib> offsety[2];

unsigned long long int rozmiary[19]={1,60,300,1500,15000L,150000L,1500000L,
	15000000L,150000000L,1500000000L,15000000000L,150000000000L,1500000000000L,
	15000000000000L,150000000000000L,1500000000000000L,15000000000000000L,150000000000000000L,1500000000000000000L};



int main()
{
	char c[18];
	int last=0;
	for(;last<18;last++)
	{
		c[last]=cin.get();
		if(c[last]<'0'||c[last]>'9')break;
	}//trzeba czytać od tyłu

		
	offsety[0].push_back(id);

	for(int i=0;i<last;i++)
	{
		int akt=last-1-i;

		Fib macrozm=jeden^rozmiary[i];
		Fib iteracyjna=id;
		for(int j=0;j*rozmiary[i]<rozmiary[i+1];j++)
		{
			for(list<Fib>::iterator it=offsety[i%2].begin();
					it!=offsety[i%2].end();
					it++)
			{
				if((((iteracyjna*(*it)).f%pow(10,i+1)))/pow(10,i)==c[akt])
				{
					offsety[(i+1)%2].push_back(iteracyjna*(*it));
					cout<<(iteracyjna*(*it)).f<<'\n';
				}
			}
			iteracyjna=iteracyjna*macrozm;

		}

		//cout<<(jeden^rozmiary[i]).f<<'\n';



		//std::cout<<c[akt];
	}
	return 0;

}