链接：https://www.nowcoder.com/questionTerminal/c0a4b917a15f40a49ca10532ab9019fb

NowCoder号称自己已经记住了1-100000之间所有的斐波那契数。
为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。当然，斐波那契数会很大。因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位。

输入描述:

输入有多组数据。
每组数据一行，包含一个整数n (1≤n≤100000)。

输出描述:

对应每一组输入，输出第n个斐波那契数的最后6位。

#include<stdio.h>
#define NO 100005
const int mod =1000000;
int main()
{   
	int a[NO]={1,2};   
	int n,i,flag=1,mark=29;//可通过打表得知f[29]>6位数 
	for(i=2;i<NO;i++)    
		a[i]=(a[i-1]+a[i-2])%mod;   
	while(scanf("%d",&n)!=EOF)  
	{      
		if(n-1>=mark)      
			printf("%06d\n",a[n-1]);   
		else     
			printf("%d\n",a[n-1]); 
	}  
	return 0;
}