A Fibonacci sequence is calculated by adding the previous two members the sequence,with the first two members being both 1.
F(1) = 1,F(2) = 1,F(3) = 1,F(4) = 1,F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4)
Your task is to take a number as input,and print that Fibonacci number.

Each line will contain an integers. Process to end of file.

For each case,output the result in a line.

  
  

   
   100
  
  

  
  

   
   4203968145672990846840663646


Note:
No generated Fibonacci number in excess of 2005 digits will be in the test data,ie. F(20) = 66526 has 5 digits.
   
   
/*
这道题的收获之处主要是会处理大数的10000进制，以后遇到情况可以处理,加油！！
Time:2014-10-20 8:07
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define MAX 10000+10
#define MM 300
#define SYS 10000000
int dig[MAX]={0,0};
int f[MAX][300];
void Get_f(){
	memset(f,sizeof(f));
	f[1][0]=1;f[2][0]=1;f[3][0]=1;f[4][0]=1;
	for(int i=5;i<MAX;i++){
		int t=0;
		for(int j=0;j<MM;j++){
			f[i][j]+=(t+f[i-1][j]+f[i-2][j]+f[i-3][j]+f[i-4][j]);
			t=f[i][j]/SYS;
			f[i][j]%=SYS;
		}
	}
}
int main(){
	int n,i;
	 Get_f();
	while(scanf("%d",&n)!=EOF){
		i=MM-1;
		while(f[n][i]==0)i--;
		printf("%d",f[n][i--]);//输出后-- 
		for(;i>=0;i--)
		printf("%07d",f[n][i]);
		puts("");
	}
return 0;
}