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
147
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.util.Queue;
import java.io.BufferedReader;
import java.util.LinkedList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class fib {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Fibonacci solver = new Fibonacci();
        solver.solve(1, in, out);
        out.close();
    }

    static class Fibonacci {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            char fib_suffix[] = in.next().toCharArray();

            int digits = fib_suffix.length;

            char current[] = new char[digits];
            Queue<Long> positions = new LinkedList<>();
            Queue<Long> nextPositions = new LinkedList<>();

            long currentMod = modFor(0);
            long nextMod = modFor(1);
            positions.add(0L);
            for (int dig = 1; dig <= digits; dig++) {
                current[digits - dig] = fib_suffix[digits - dig];
                nextPositions = new LinkedList<>();
                while (!positions.isEmpty()) {
                    long start = positions.remove();
                    for (long j = start; j < nextMod; j += currentMod) {
                        long cand = fib(j).longValue();
                        if (suffix(cand, dig) == Long.valueOf(new String(current, digits - dig, dig))) {
                            nextPositions.add(j);
                        }
                    }
                }
                if (nextPositions.isEmpty()) {
                    out.println("NIE");
                    return;
                }
                positions.addAll(nextPositions);
                currentMod = nextMod;
                nextMod = modFor(dig + 1);
            }
            out.println(nextPositions.remove());
        }

        private long suffix(long cand, int digits) {
            return cand % pow(10, digits);
        }

        private long modFor(int d) {
            if (d == 0) return 1;
            if (d == 1) return 60;
            if (d == 2) return 300;
            if (d == 19) return 0;
            return 15L * pow(10, d - 1);
        }

        private long pow(int n, int k) {
            long ans = 1;
            for (int i = 0; i < k; i++) {
                ans *= n;
            }
            return ans;
        }

        private BigInteger fib(long n) {
            if (n == 0) return BigInteger.ZERO;
            Macierz m = new Macierz(BigInteger.ONE, BigInteger.ONE, BigInteger.ONE, BigInteger.ZERO);
            return Macierz.power(m, n - 1).a11;
        }

        private static class Macierz {
            private static Macierz jednostkowa = new Macierz(BigInteger.ONE, BigInteger.ZERO, BigInteger.ZERO, BigInteger.ONE);
            private BigInteger a11;
            private BigInteger a12;
            private BigInteger a21;
            private BigInteger a22;
            private BigInteger MOD = new BigInteger("1000000000000000000");

            public Macierz(BigInteger a11, BigInteger a12, BigInteger a21, BigInteger a22) {
                this.a11 = a11;
                this.a12 = a12;
                this.a21 = a21;
                this.a22 = a22;
            }

            public Macierz multiMod(Macierz m) {
                BigInteger b11 = a11.multiply(m.a11).add(a12.multiply(m.a21)).mod(MOD);
                BigInteger b12 = a11.multiply(m.a12).add(a12.multiply(m.a22)).mod(MOD);
                BigInteger b21 = a21.multiply(m.a11).add(a22.multiply(m.a21)).mod(MOD);
                BigInteger b22 = a21.multiply(m.a12).add(a22.multiply(m.a22)).mod(MOD);
                return new Macierz(b11, b12, b21, b22);
            }

            public static Macierz power(Macierz m, long n) {
                if (n == 0) return Macierz.jednostkowa;
                if (n % 2 == 0) {
                    return power(m.multiMod(m), n / 2);
                }
                return m.multiMod(power(m, n - 1));
            }

        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

    }
}