import java.io.*;
import java.util.*;
import java.math.*;

public class FastFibonacci {

  public static int numMultiplications = 0;

  public static void main(String [] args) {

    int n = Integer.parseInt(args[0]);
    BigInteger fibN = fib(n);
    System.out.println("numMatrixMultiplications = " + numMultiplications);
    System.out.println("Fib " + n + " = " + fibN);

  }


  public static BigInteger fib(int originalExponent) {

    if (originalExponent == 0) return BigInteger.ZERO;
    if (originalExponent == 1) return BigInteger.ONE;
    
    numMultiplications = 0;

    BigInteger[][] base = new BigInteger[][]{{BigInteger.ONE,BigInteger.ONE},
					     {BigInteger.ONE,BigInteger.ZERO}};

    BigInteger[][] product = power( base, originalExponent - 1);

    return product[0][0];

  }


  public static BigInteger[][] power(BigInteger[][] base, int exponent) {
    if (exponent == 1) return base;

    BigInteger[][] intermediate = power(base, exponent/2);
    BigInteger[][] result = multiply(intermediate,intermediate);
    numMultiplications++;

    if ((exponent & 1) == 1) {
      numMultiplications++;
      return multiply( result, base);
    }

    return result;
  }


  public static BigInteger[][] multiply( BigInteger[][] a, BigInteger[][] b) {
    BigInteger[][] result = new BigInteger[ a.length ] [ b[0].length ];

    for( int i = 0; i < a.length; i++) {
      for (int j = 0; j < b[0].length; j++) {
	BigInteger total = BigInteger.ZERO;
	for (int k = 0; k < a[i].length; k++) {
	  BigInteger product = a[i][k].multiply(b[k][j]);
	  total = total.add( product );
	}
	result[i][j] = total;
      }
    }

    return result;
  }
    
}