class Fibber {

public static long badFib(int n) {
  if (n==0) return 1;
  if (n==1) return 1;
  return (badFib(n-1)+badFib(n-2));
}

public static long goodFib(int n) {
  if (n==0) return 1;
  return goodFibR(n,1,1);
}

public static long goodFibR(int n, long prev1, long prev2) {
  if (n==0) return prev1;
  return goodFibR(n-1,prev2, prev1+prev2);
}


public static void main (String[] args) {

  long sT, eT, res;
  
  int NUM = Integer.parseInt(args[0]);
  
  /* badFib is O(2^N) runtime */
/*
  System.out.println(badFib(0));  
  System.out.println(badFib(1));
  System.out.println(badFib(2));
  System.out.println(badFib(3));
  System.out.println(badFib(4));
  System.out.println(badFib(5));
  System.out.println(badFib(6));
  System.out.println(badFib(7));
 
  sT = System.nanoTime();
  res = badFib(NUM);
  eT = System.nanoTime();
  System.out.println("fib("+NUM+") is "+ res + " in "+(eT-sT)+" units");
  System.out.println();
*/
  
  /* goodFib is O(N) runtime */
/*
  System.out.println(goodFib(5));  
  System.out.println(goodFib(10));
  System.out.println(goodFib(20));
  System.out.println(goodFib(30));
  System.out.println(goodFib(40));
  System.out.println(goodFib(50));
  System.out.println(goodFib(60));
  System.out.println(goodFib(70));
*/
  sT = System.nanoTime();
  res = goodFib(NUM);
  eT = System.nanoTime();
  System.out.println("fib("+NUM+") is "+ res + " in "+(eT-sT)+" units");
  System.out.println();

}