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
140
141
142
143
144
145
146
//package fib;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;



public class fib {
	static BigInteger in;
	static BigInteger k;
	
	static BigInteger mod;
	static int modsize;
	static BigInteger b1 = B("1");
	static BigInteger b0 = B("0");
	static BigInteger b1500 = B("1500");
	static BigInteger b10 = B("10");
	static BigInteger b100 = B("100");

	
	static public class Mat {
		BigInteger a,b;
		BigInteger c,d;
		Mat(BigInteger a2,BigInteger b2,BigInteger c2,BigInteger d2) {
			a=a2; b=b2; c=c2;d=d2;
		}
		public Mat mul(Mat y) {
			return new Mat(
					a.multiply(y.a).add(b.multiply(y.c)).mod(mod),
					a.multiply(y.b).add(b.multiply(y.d)).mod(mod),
					c.multiply(y.a).add(d.multiply(y.c)).mod(mod),
					c.multiply(y.b).add(d.multiply(y.d)).mod(mod)
				);
		}
	}
	
	static BigInteger B(String s){
		return new BigInteger(s);
	}
	
	static boolean comp(Mat x, Mat step, BigInteger stepB, BigInteger mmod, int msize) {
		if(x.a.mod(mmod).compareTo(in.mod(mmod)) == 0) {
			if(msize >= modsize) {
//				System.out.println(x.a.toString());
				return true;
			} else {
				msize++;
				BigInteger nk = b0;
				Mat step10 = step.mul(step).mul(step).mul(step).mul(step);
				step10 = step10.mul(step10);
				BigInteger stepB10 = stepB.multiply(b10);
				BigInteger mmod10 = mmod.multiply(b10);
				for(int i=0;i<20;i++) {
//					System.out.println("msize:" + Integer.toString(msize) + " k: " + k.toString() + " nk: "+ nk.toString() + " " + Integer.toString(i) + " " + x.a.toString());
					if(comp(x, step10, stepB10, mmod10, msize)) {
						k = k.add(nk);
						return true;
					}
					x = step.mul(x);
					nk = nk.add(stepB);
				}
				return false;
			}
		}
		return false;
	}
	static void print(Mat m) {
		System.out.println(m.a.toString() + " " + m.b.toString());
		System.out.println(m.c.toString() + " " + m.d.toString());
	}

	public static void main(String[] args) {
		String s="";
		try {
		        BufferedReader bufferRead = new BufferedReader(new InputStreamReader(System.in));
		        s = bufferRead.readLine().trim();
		} catch(IOException e) {
		    e.printStackTrace();
		}		
		
//		System.out.println(" in: " + s);
		modsize = s.length();
		mod = b10.pow(modsize);
		in = B(s);
				
		Mat fn = new Mat(B("1"),B("1"),
				         B("1"),B("0"));

		Mat f1 = new Mat(B("1"),B("0"),
		         		 B("0"),B("1"));


		k = b100;

/*		for(int i=0;i<100;i++) {
			f0=fn.mul(f0);
		}*/
		Mat fpocz;
		fpocz = fn.mul(fn);
		fpocz = fpocz.mul(fpocz);
		fpocz = fpocz.mul(fpocz).mul(fpocz).mul(fpocz).mul(fpocz);
		fpocz = fpocz.mul(fpocz).mul(fpocz).mul(fpocz).mul(fpocz);
		
		fpocz = fpocz.mul(new Mat(B("0"),B("0"),
		         B("1"),B("0")));


		Mat f2 = fn.mul(fn);
		Mat f3 = f2.mul(fn);
		Mat f5 = f3.mul(f2);
		BigInteger fb1500 = b1500;

		int msize = 3;

		Mat f1500 = f1;
/*		for(int i=0;i<1500;i++) {
			f1500 = f1500.mul(fn);
//			fb1500 = fb1500.add(b1);
		}*/
		//1500: 2 2 3 5 5 5
		f1500 = fn.mul(fn);
		f1500 = f1500.mul(f1500);
		f1500 = f1500.mul(f1500).mul(f1500);
		f1500 = f1500.mul(f1500).mul(f1500).mul(f1500).mul(f1500);
		f1500 = f1500.mul(f1500).mul(f1500).mul(f1500).mul(f1500);
		f1500 = f1500.mul(f1500).mul(f1500).mul(f1500).mul(f1500);

	//	print(f1500);

		if(modsize < msize) msize = modsize;

		BigInteger mmod = b10.pow(msize);

		for(int i=0;i<1500;i++) {
			fpocz=fn.mul(fpocz);
			k=k.add(b1);
			if(comp(fpocz, f1500, fb1500, mmod, msize)) {
				System.out.println(k.toString());
				return;
			}
		}
		System.out.println("NIE");
	}
}