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
148
149
150
151
152
153
154
155
import javafx.util.Pair;

import java.math.BigInteger;
import java.util.*;

public class fib {

    private final BigInteger MOD = new BigInteger("1000000000000000000");

    private class Matrix {
        BigInteger a, b, c, d;
        BigInteger count;

        Matrix() {
        }

        Matrix(BigInteger a, BigInteger b, BigInteger c, BigInteger d) {
            this.a = a;
            this.b = b;
            this.c = c;
            this.d = d;
        }

        @Override
        public boolean equals(Object obj) {
            Matrix m = (Matrix) obj;
            return m.a.equals(this.a)
                    && m.b.equals(this.b)
                    && m.c.equals(this.c)
                    && m.d.equals(this.d);
        }

        @Override
        public int hashCode() {
            return Objects.hash(a, b, c, d);
        }

        @Override
        public String toString() {
            return a + ", " + b + ", " + c + ", " + d;
        }
    }

    private Matrix times(Matrix m1, Matrix m2) {
        Matrix res = new Matrix();
        res.a = ((m1.a.multiply(m2.a)).add(m1.b.multiply(m2.c))).mod(MOD);
        res.b = ((m1.a.multiply(m2.b)).add(m1.b.multiply(m2.d))).mod(MOD);
        res.c = ((m1.c.multiply(m2.a)).add(m1.d.multiply(m2.c))).mod(MOD);
        res.d = ((m1.c.multiply(m2.b)).add(m1.d.multiply(m2.d))).mod(MOD);
        return res;
    }

    HashMap<Pair<Long, Matrix>, Matrix> cache = new HashMap<Pair<Long, Matrix>, Matrix>();
    private Matrix pow(long k, Matrix m) {
        if (cache.containsKey(new Pair<Long, Matrix>(k, m)) && k < 1000000){
            return cache.get(new Pair<Long, Matrix>(k, m));
        }
        if (k == 0) {
            return new Matrix(new BigInteger("1"), new BigInteger("0"), new BigInteger("0"), new BigInteger("1"));
        }

        if (k <= 1) {
            return m;
        }
        if (k % 2 == 0) {
            return pow(k / 2, times(m, m));
        } else {
            Matrix mat =times(m, pow(k / 2, times(m, m)));
            cache.put(new Pair<Long, Matrix>(k, m), mat);
            return mat;
        }
    }

    private void testMatrix() {
        Matrix m = new Matrix(new BigInteger("1"), new BigInteger("1"), new BigInteger("1"), new BigInteger("0"));
        Matrix res = pow(12, m);
        assert (res.a.longValue() == 233);
        assert (res.b.longValue() == 144);
        assert (res.c.longValue() == 144);
        assert (res.d.longValue() == 89);


    }

    private Matrix getFib(long k) {
        Matrix zero = new Matrix(new BigInteger("0"), new BigInteger("0"), new BigInteger("0"), new BigInteger("0"));
        Matrix one = new Matrix(new BigInteger("1"), new BigInteger("0"), new BigInteger("0"), new BigInteger("0"));
        Matrix two = new Matrix(new BigInteger("1"), new BigInteger("0"), new BigInteger("0"), new BigInteger("0"));
        if (k == 0) return zero;
        if (k == 1) return one;
        if (k == 2) return two;
        Matrix start = new Matrix(new BigInteger("1"), new BigInteger("1"), new BigInteger("0"), new BigInteger("0"));
        Matrix mul = new Matrix(new BigInteger("1"), new BigInteger("1"), new BigInteger("1"), new BigInteger("0"));
        return times(mul, pow(k - 2, mul));
    }

    private BigInteger getMod(String line) {
        BigInteger mod = new BigInteger("1" + line);
        BigInteger mod2 = new BigInteger(line);
        return mod.subtract(mod2);
    }


    private void solve(String line) {
        //testMatrix();

        BigInteger modul = getMod(line);
        BigInteger nr = new BigInteger(line);


        BigInteger m = new BigInteger("10");
        BigInteger cycle = new BigInteger("15");
        List<Matrix> next = new LinkedList<Matrix>();
        for (long k = 1; k < 200; k++) {
            Matrix mat = getFib(k);
            mat.count = new BigInteger(String.valueOf(k));
            if (mat.a.mod(m).equals(nr.mod(m))) {
                next.add(mat);
            }
        }


        while (modul.compareTo(m) >= 0) {
            List<Matrix> current = next;
            next = new LinkedList<Matrix>();
            for (Matrix matrix : current) {
                for (long i = 0; i <= 10; i++) {
                    Matrix res = times(matrix, pow(cycle.longValue() * i, new Matrix(new BigInteger("1"), new BigInteger("1"), new BigInteger("1"), new BigInteger("0"))));
                    res.count = matrix.count.add(cycle.multiply(new BigInteger(String.valueOf(i))));
                    if (res.a.mod(m).equals(nr.mod(m))) {
                        next.add(res);
                        if (modul.compareTo(m) == 0) {
                            System.out.print(res.count);
                            return;
                        }
                    }
                }
            }
            cycle = cycle.multiply(new BigInteger("10"));
            m = m.multiply(new BigInteger("10"));
        }
        System.out.println("NIE");


    }

    public static void main(String args[]) {
        fib a = new fib();
        Scanner scanner = new Scanner(System.in);
        //while (true) {
            String line = scanner.nextLine();
            a.solve(line);
        //}
    }
}