Fibo

#include<stdio.h>
#include<stdlib.h>
int Fibo(int);
int main()
{
	int N, n;
	scanf("%d", &N);
	while(N--)
	{
		scanf("%d", &n);
		printf("%d\n", Fibo(n));
	}
}
int Fibo(int N)
{
	if(N <= 2)
		return N>0;
	int f1 = 1, f2 = 1;
	N -= 2;
	while(N--)
	{
		f1 = f1+f2;
		f2 = f1-f2;
		if(f2 > 10000000)
		{
			f1 -= 10000000;
			f2 -= 10000000;
		}
	}
	return f1%10000000;
}