class fib {
 // Method fib.f(n) returns the n'th Fibonacci number
 // It uses ALGORITHM 1A: BINARY RECURSION
 private static long f(long n) {
  return n<2 ? 1 : f(n-2)+f(n-1);
 }
 // Method fib.f_print(n) prints the nth Fibonacci number
 private static void f_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method fib.main is the program entry point
 public static void main(String argv[]) {
  f_print(46);
 }
}

import java.math.BigInteger;  // Required for arbitrary precision numbers
import java.util.Vector;      // Required for arbitrary length arrays
// Class FibArray is an approximation of an infinite
// list of Fibonacci numbers.
class FibArray {
 private static Vector numbers;
 public FibArray() {
  numbers=new Vector();
  numbers.addElement(BigInteger.ONE);
  numbers.addElement(BigInteger.ONE);
 }
 public static BigInteger elementAt(int index) {
  try {
    return (BigInteger)numbers.elementAt(index);
  } catch (ArrayIndexOutOfBoundsException r) {
    numbers.addElement(
        ((BigInteger)numbers.elementAt(numbers.size()-2)).add(
        (BigInteger)numbers.elementAt(numbers.size()-1))
       );
    return (elementAt(index-1).add(elementAt(index-2)));
  }
 }
}
class fib {
 // Method fib.f(n) returns the n'th Fibonacci number
 // It uses ALGORITHM 2A-2: LIST WITH EXCEPTIONS
 private static BigInteger f(int n) {
  return (new FibArray()).elementAt(n);
 }
 // Method fib.f_print(n) prints the nth Fibonacci number
 private static void f_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method fib.main is the program entry point
 public static void main(String argv[]) {
  f_print(10000);
 }
}

import java.math.BigInteger; // Required for arbitrary precision arythmetics
class fib {
 private static BigInteger l(BigInteger x1, BigInteger x2, long c) {
  return c<2 ? x1 : l(x1.add(x2), x1, c-1);
 }
 // Method fib.f(n) returns the n'th Fibonacci number
 // It uses ALGORITHM 2B: SIMPLE RECURSION
 private static BigInteger f(long n) {
  return l(new BigInteger("1"),new BigInteger("1"),n);
 }
 // Method fib.f_print(n) prints the nth Fibonacci number
 private static void f_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method fib.main is the program entry point
 public static void main(String argv[]) {
  f_print(10000);
 }
}

import java.math.BigInteger; // Required for arbitrary precision arythmetics
class fib {
 // Method fib.f(n) returns the n'th Fibonacci number
 // It uses ALGORITHM 2C: NON-RECURSIVE LOOP
 private static BigInteger f(long n) {
  BigInteger x1 = new BigInteger("1");
  BigInteger x2 = new BigInteger("1");
  BigInteger tmp;
  for(long i=1;i<=n;i++) {
   x1=x1.add(x2);
   tmp=x2; x2=x1; x1=tmp;
  }
  return x1;
 }
 // Method fib.f_print(n) prints the nth Fibonacci number
 private static void f_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method fib.main is the program entry point
 public static void main(String argv[]) {
  f_print(10000);
 }
}

import java.math.BigInteger; // Required for arbitrary precision arythmetics
class fib {
 private static BigInteger[][] mm(BigInteger[][] a,BigInteger[][] b)
 {
  BigInteger[][] c = new BigInteger[a.length][b[0].length];
  for(int i=0;i<a.length;i++)
   for(int j=0;j<b[0].length;j++) {
    c[i][j] = new BigInteger("0");
    for(int k=0;k<b.length;k++)
     c[i][j] = c[i][j].add(a[i][k].multiply(b[k][j]));
   }
   return c;
 }
 // Method mp(M,n) raises the matrix M into n'th power
 private static BigInteger[][] mp(BigInteger[][] M, int n) {
  if(n>1) {
   BigInteger[][] b = mp(M, n/2);
   if (n%2 == 1) { return mm(mm(b,b),M); } else { return mm(b,b); }
  } else { return M; }
 }
 // Method fib.f(n) returns the n'th Fibonacci number
 // It uses ALGORITHM 3A: MATRIX EQUATION
 private static BigInteger f(int n) {
  BigInteger[][] a = {{new BigInteger("1"),new BigInteger("1")},
                      {new BigInteger("1"),new BigInteger("0")}};
  return mp(a,n)[0][0];
 }   
 // Method fib.f_print(n) prints the nth Fibonacci number
 private static void f_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method fib.main is the program entry point
 public static void main(String argv[]) {
  f_print(1000000);
 }
}

import java.math.BigInteger; // Required for arbitrary precision arythmetics
class fib {
 private static BigInteger[] l(long n) {
  BigInteger[] k = new BigInteger[2];
  BigInteger[] l = new BigInteger[2];
  if(n<2)  { k[0]=new BigInteger("1"); k[1]=new BigInteger("1"); return k; }
  if(n==2) { k[0]=new BigInteger("2"); k[1]=new BigInteger("1"); return k; }
  if((n%2)==1) {
    k = l((n-1)/2);
    l[0]=k[0].multiply((k[0].add(k[1]))).add(k[0].multiply(k[1]));
    l[1]=k[0].multiply(k[0]).add(k[1].multiply(k[1]));
  } else {
    k = l((n/2)-1);
    l[0]=(k[0].add(k[1])).multiply((k[0].add(k[1]))).add(k[0].multiply(k[0]));
    l[1]=(k[0].add(k[1])).multiply(k[0]).add(k[0].multiply(k[1]));
  }
  return l;
 }
 // Method fib.f(n) returns the n'th Fibonacci number
 // It uses ALGORITHM 3B: FAST RECURSION
 private static BigInteger f(long n) {
  return l(n)[0];
 }
 // Method fib.f_print(n) prints the nth Fibonacci number
 private static void f_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method fib.main is the program entry point
 public static void main(String argv[]) {
  f_print(1000000);
 }
}

class fib {
 // Method fib.f(n) returns the n'th Fibonacci number
 // It uses ALGORITHM 3C: BINET'S FORMULA
 private static long f(long n) {
  double phi  = (1+Math.sqrt(5))/2;
  return Math.round((Math.pow(phi, n+1) - Math.pow(1-phi, n+1)) / Math.sqrt(5));
 }
 // Method fib.f_print(n) prints the nth Fibonacci number
 private static void f_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method fib.main is the program entry point
 public static void main(String argv[]) {
  f_print(69);
 }
}