public class Fib
{
  public static long fib(int n)
  {
    if(n == 0)
    {
      return 0;
    }
    else if (n == 1 || n == 2)
    {
      return 1;
    }
    Matrix m = new Matrix(1, 1, 1, 0);
    Matrix m2 = matPow(m, n-1);
    return m2.getElement(0, 0);
  }
  
  public static Matrix matPow(Matrix m, int p)
  {
    if(p == 0)
      return new Matrix();//identity matrix
    else if(p == 1)
      return m;
    else
    {
      Matrix temp = matPow(m, p/2);
      temp = temp.times(temp);
      if(p % 2 == 1)
        temp = temp.times(new Matrix(1, 1, 1, 0));
      return temp;
    }
  }

  public static long sumFib(int n)
  {
    return fib(n+2) - 1;
  }
    
  public static void main(String args[])
  {
    for(int i = 0; i < 90; i++)
    {
      System.out.println("i:" + i + " fib("+i+")=" + fib(i) + " sum = " + sumFib(i));
    }
  }
}