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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

/**
 *
 * @author felke
 */
public class fib {
    
    private static final BigInteger max = new BigInteger("10000000000000000000");
    
    private static final long[] levelValue = new long[19];
    private static final int[] levelCount = new int[19];

    private static BigInteger multiply(BigInteger x, BigInteger y) {
        BigInteger result = x.multiply(y);
        return result.mod(max);
    }

    private static BigInteger fastFibonacciDoubling(long n) {
        BigInteger a = BigInteger.ZERO;
        BigInteger b = BigInteger.ONE;
        int m = 0;
        for (int i = 64 - Long.numberOfLeadingZeros(n); i >= 0; i--) {

            BigInteger d = multiply(a, b.shiftLeft(1).subtract(a));
            BigInteger e = multiply(a, a).add(multiply(b, b));
            a = d;
            b = e;
            m *= 2;

            if (((n >>> i) & 1) != 0) {
                BigInteger c = a.add(b);
                a = b;
                b = c;
                m++;
            }
        }
        return a;
    }
    
    
    private static void fillLevelValues()
    {
        levelValue[0]=1;
        levelCount[0]=61;
        levelValue[1]=60;
        levelCount[1]=6;
        levelValue[2]=300;
        levelCount[2]=6;
        levelValue[3]=1500;
        levelCount[3]=11;
        for(int k=4;k<19;k++)
        {
            levelValue[k] = levelValue[k-1]*10;
            levelCount[k] = 11;
        }
        
    }
    
    
    private static Long calculate(long result, String value, int level)
    {        
        if(level == value.length()){
            return result;
        }
        
        //System.out.println(result + " " + value + " " + level);
        
        for(int k=0; k<levelCount[level]; k++)
        {
            BigInteger fib = fastFibonacciDoubling(result);
            //System.out.println(level + ": " + result + " " + fib);
            //System.out.println("Examining: " + result + ": " + fib);
            
            
            Character extractedDigit = extractDigit(fib, level);
            if(extractedDigit != null && extractDigit(fib, level).equals(value.charAt(value.length()-level-1)))
            {
                Long solution = calculate(result, value, level+1);
                if(solution != null)
                {
                    return solution;
                }
            }
            
            result+= levelValue[level]; 
        }
        
        return null;
    }
    
    private static Character extractDigit(BigInteger number, int level)
    {
        String s = number.toString();
        
        if (s.length()>level)
        {
            return s.charAt(s.length()-level-1);
        }
        return null;
    }

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
               
        String value = br.readLine();

        fillLevelValues();
        Long result;
        
        result = calculate(0, value, 0);
        
        if(result == null){
            System.out.println("NIE");
        }
        else
        {
            System.out.println(result);
        }
    }
}