/*
#include <stdio.h>
int memo[1000]= {};
int f(int n)
{
if(n==1||n==2)
{
return memo[n]=1;
}
if(memo[n]!=0)
{
return memo[n]%10009;
}
return memo[n]=f(n-1)%10009+f(n-2)%10009;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", f(n)%10009);
return 0;
}
*/
/*
#include<stdio.h>
int memo[10000]= {};
int f(int n)
{
if(n==1)
{
return memo[n]=1;
}
else if(n==2)
{
return memo[n]=2;
}
if(memo[n]!=0)
{
return memo[n]%100000007;
}
return memo[n]=f(n-1)%100000007+f(n-2)%100000007;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", f(n)%100000007);
return 0;
}
*/
/*
#include<stdio.h>
int memo[10000]= {};
int f(int n)
{
if(n%3!=0)
{
return 0;
}
if(memo[n]!=0)
{
return memo[n];
}
if(n==3) return 2;
return memo[n] = f(n-3)*2%100000007;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", f(n)%100000007);
return 0;
}
*/