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
import static java.math.BigInteger.ONE;
import static java.math.BigInteger.TEN;
import static java.math.BigInteger.ZERO;

import java.math.BigInteger;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;

public class fib {
  private static final BigInteger[] identity = new BigInteger[] { ZERO, ONE, ZERO, ONE };
  private static final BigInteger[] transitionOne = new BigInteger[] { ONE, ZERO, ONE, ONE };
  private static final String ENTRANCE = "ENTRANCE";

  private static BigInteger scope;

  public static void main(String... args) {
    Scanner scanner = new Scanner(System.in);
    BigInteger ending = scanner.nextBigInteger();
    scope = TEN.pow(ending.toString(10).length());
    scanner.close();

    Map<String, BigInteger[]> graph = new HashMap<>();
    BigInteger lastDigit = ending.mod(TEN);

    BigInteger[] start = identity;
    BigInteger[] shift = identity;
    BigInteger[] stop = new BigInteger[0];
    while (true) {
      shift = joinScoped(shift, transitionOne);
      stop = joinScoped(start, shift);
      if (digit(0, stop[2]).equals(lastDigit)) {
        String startKey = key(0, start);
        String stopKey = key(0, stop);
        graph.put(startKey, shift);
        if (graph.containsKey(stopKey)) {
          break;
        }
        shift = identity;
        start = stop;
      }
    }

    HashSet<String> visited = new HashSet<>();

    for (int position = 1; position < ending.toString().length(); position++) {
      BigInteger digit = digit(position, ending);
      Map<String, BigInteger[]> newGraph = new HashMap<>();

      start = identity;
      shift = graph.get(ENTRANCE);

      while (true) {
        stop = joinScoped(start, shift);
        String startKey = key(position, start);
        String stopKey = key(position, stop);
        if (digit(position, stop[2]).equals(digit)) {
          newGraph.put(startKey, shift);
          if (newGraph.containsKey(stopKey)) {
            break;
          }
          shift = identity;
          start = stop;
          visited.clear();
        } else {
          if (visited.contains(stopKey)) {
            visited.clear();
            break;
          } else {
            visited.add(stopKey);
          }
        }
        shift = joinScoped(shift, graph.get(key(position - 1, stop)));
      }

      graph = newGraph;
      if (graph.isEmpty()) {
        break;
      }

    }
    if (graph.isEmpty()) {
      System.out.println("NIE");
    } else {
      BigInteger number = graph.get(ENTRANCE)[0];
      if (number.compareTo(TEN.pow(100)) < 0) {
        System.out.println(number);
      } else {
        System.out.println("NIE");
      }
    }
  }

  private static String key(int position, BigInteger[] node) {
    return node == identity
        ? ENTRANCE
        : "" + node[1].mod(TEN.pow(position + 1)) + ":"
            + node[2].mod(TEN.pow(position + 1));
  }

  private static BigInteger digit(int position, BigInteger number) {
    return number.divide(TEN.pow(position)).mod(TEN);
  }

  private static BigInteger[] join(BigInteger[] elementA, BigInteger[] elementB) {
    BigInteger n = elementA[0];
    BigInteger fnm1 = elementA[1];
    BigInteger fn = elementA[2];
    BigInteger fnp1 = elementA[3];

    BigInteger k = elementB[0];
    BigInteger fkm1 = elementB[1];
    BigInteger fk = elementB[2];
    BigInteger fkp1 = elementB[3];

    BigInteger s = n.add(k);
    BigInteger fsm1 = fnm1.multiply(fkm1).add(fn.multiply(fk));
    BigInteger fs = fn.multiply(fkm1).add(fnp1.multiply(fk));
    BigInteger fsp1 = fn.multiply(fk).add(fnp1.multiply(fkp1));

    return new BigInteger[] { s, fsm1, fs, fsp1 };
  }

  private static BigInteger[] joinScoped(BigInteger[] elementA, BigInteger[] elementB) {
    BigInteger[] joined = join(elementA, elementB);
    return new BigInteger[] { joined[0], joined[1].mod(scope), joined[2].mod(scope),
        joined[3].mod(scope) };
  }
}