import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
public class ProjectEuler{
static Map<Integer,BigInteger> mapping = new HashMap<Integer,BigInteger>();
public static void main(String[] args){
mapping.put(0, BigInteger.ZERO);
mapping.put(1, BigInteger.ONE);
for(int i=2;i<999;i++){
mapping.put(i, (new BigInteger("-1")));
}
//fibonnaci for 0 to 10
for(int i=0;i<11;i++){
System.out.println(fibonnaci(i));
}
}
public static BigInteger fibonnaci(int n){
//if n==0
if(n<1){
return mapping.get(0);
}
//if n==1
if(n<2){
return mapping.get(1);
}
//if in memory
if(!(mapping.get(n).equals(-1))){
return mapping.get(n);
}
//if not in memory
BigInteger bg = fibonnaci(n-1).add(fibonnaci(n-2));
mapping.put(n, bg);
return mapping.get(n);
}
}