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
//FIB
#include <cstdio>
#include <iostream>
#include <sstream>
#include <string>
using namespace std;

long long int endd;
long long int modula;
int digitsNum;
int cnt;
long long int Czyzby;


long long int mulmod(long long int a,long long int b,long long int c)
{
    if (a<=1000000000LL && b<=1000000000LL)
    {
        long long int ret = ((a%c)*(b%c))%c;
        return ret;
    }

    long long int ret = 0LL;
    a = a%c;

    while (b > 0LL)
    {
        if(b&1LL)
        {
            ret = (ret+a)%c;
        }
        a = (a<<1LL)%c;
        b>>=1LL;
    }

    return ret%c;
}

#define FOO(a,b,c,d,m) ((mulmod(a,b,m) + mulmod(c,d,m))%(m))

void multiply(long long int F[2][2], long long int M[2][2], const long long int modulo_x)
{
    long long int x =  FOO(F[0][0], M[0][0], F[0][1], M[1][0], modulo_x);
    long long int y =  FOO(F[0][0], M[0][1], F[0][1], M[1][1], modulo_x);
    long long int z =  FOO(F[1][0], M[0][0], F[1][1], M[1][0], modulo_x);
    long long int w =  FOO(F[1][0], M[0][1], F[1][1], M[1][1], modulo_x);

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}


/* Optimized version of power() in method 4 */
void power(long long int F[2][2], long long int n, const long long int modulo_x)
{
  if( n == 0 || n == 1)
      return;
  long long int M[2][2] = {{1,1},{1,0}};

  power(F, n/2, modulo_x);
  multiply(F, F, modulo_x);

  if (n%2 != 0)
     multiply(F, M, modulo_x);
}



/// DEFINITIONS

/* function that returns nth Fibonacci number */
long long int fib(long long int n, const long long int modulo_x)
{
    long long int F[2][2] = {{1,1},{1,0}};
    if (n == 0)
        return 0;
    power(F, n-1, modulo_x);
    return F[0][0];
}

long long int step(int i)
{
    if(i==0)
        return 1;
    if(i==1)
        return 60;
    if(i==2)
        return 300;
    long long int a=1500;
    for(int j=3;j<i;j++)
        a*=10;
    return a;
}

int endsMatches( long long int i ,int pos)
{
    long long int dec=10;
    for( int k=1;k<pos;k++)
        dec*=10;
    if( (i%dec) == (endd%dec) )
        return 1;
    else
        return 0;
}

void checkNumber( int position, long long int parent_num )
{
    long long int inc=step(position-1);
    long long int range=step(position)+parent_num;
    //something with begining shorter than x numbers
    for(long long int i=parent_num; i<range; i+=inc )
    {        
        //  long long int my_fib=fib_modulo(i);
        long long int my_fib=fib(i,modula);
       // printf("my_fib(%lld)=%lld\n",i,my_fib);
        if ( endsMatches(my_fib,position) )
        {
            if( position<=digitsNum )
                checkNumber(position+1,i);
            else
                Czyzby=i;
        }
        if(Czyzby!=0)
            break;
    }
}



int main()
{
    //test against 248205484613618008 -->  144326669924773506
    //endd=248205484613618008LL;
    Czyzby==0;
    scanf("%lld",&endd);
    modula=10;
    for(digitsNum=1; digitsNum<18; digitsNum++ )
    {
        modula*=10;
        if( modula>endd )
            break;
    }
    checkNumber( 1 , 1 );
    if(Czyzby==0)
        printf("NIE\n");
    else
    {
        printf("%lld\n",Czyzby);
    }
    return 0;
}