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
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int64;
int64 MOD;

int64 x, x_size;
int64 A, B, C, D, a, b, c, d, u, i, o, p, j;
vector<int64> v[20];

int64 wczytaj(){
    string a;
    cin >> a;
    x_size = a.size();
    int64 y = 0;
    for( j = 0; j<a.size(); j++ ){
        y += a[j]-48;
        y *= 10;
    }
    y /= 10;
    return y;
}

int64 fib(int64 n){
    n--;
    A = D = 1;
    B = C = 0;
    a = b = c = 1;
    d = 0;
    while( n ){
        if( n%2==1 ){
            u = A, i = B, o = C, p = D;
            A = ((u*a)%MOD+(i*c)%MOD)%MOD;
            B = ((u*b)%MOD+(i*d)%MOD)%MOD;
            C = ((o*d)%MOD+(u*c)%MOD)%MOD;
            D = ((p*d)%MOD+(i*c)%MOD)%MOD;
        }
        n /= 2;
        u = a, i = b, o = c, p = d;
        a = ((u*u)%MOD + (i*o)%MOD)%MOD;
        b = ((u*i)%MOD + (i*p)%MOD)%MOD;
        c = ((o*p)%MOD + (u*o)%MOD)%MOD;
        d = ((p*p)%MOD + (i*o)%MOD)%MOD;
    }
    return A;
}

void brut(){
    int64 mod = 10;
    for( int j = 1; j<x_size; j++ )
        mod *= 10;
    for( int j = 1; j<=1500; j++ ){
        if( fib((int64)j)%mod==x ){
            printf("%d\n", j);
            return;
        }
    }
}

void wzorcowka(){
    for( int j = 1; j<60; j++ )
        if( fib(j)%10==x%10 )
            v[1].push_back(j);
    int64 A = 60, K = 300;
    int64 mod = 100;
    for( int j = 2; j<=x_size; j++ ){
        for( int k = 0; k<v[j-1].size(); k++ ){
            for( int l = 0; A*l+v[j-1][k]<K; l++ ){
                //if( j==2 )printf("%llu %llu %llu\n", fib(A*l+v[j-1][k]), mod, x);
                if( fib(A*l+v[j-1][k])%mod==x%mod ){
                    //printf("2");
                    v[j].push_back(A*l+v[j-1][k]);
                }
            }
        }
        if( A==60 )A=300;
        else if( A==300 )A=1500;
        else A*=10;
        if( K==300 )K=1500;
        else K*=10;
        mod*=10;
    }
    if( v[x_size].size()==0 )
        printf("NIE\n");
    else
        printf("15000000000000000000000000%llu\n", v[x_size][0]);
    /*for( int i = 0; i<=x_size; i++ ){
        for( int j = 0; j<v[i].size(); j++ )
            printf("%llu ", v[i][j]);
        printf("\n");
    }*/
};

int main()
{
    x = wczytaj();
    MOD=10;
    for( int i = 0; i<x_size; i++ )
        MOD*=10;
    wzorcowka();
    return 0;
}