//#include <stdio.h>
//int s=1,n,r;
//int fac(int a,int b)
//{
// if(a==b)
// {
// return b;
// }
// return a*fac(a-1,b);
//}
//int main()
//{
// int a,b=1,c=1;
// scanf("%d %d",&n,&r);
// if(r>=n-r)
// {
// a=fac(n,r+1);
// b=fac(n-r,1);
// }
// else
// {
// a=fac(n,n-r+1);
// b=fac(r,1);
// }
// printf("%d",a/(b*c));
//}
//#include <stdio.h>
//int memo[10000]={};
//int f(int a)
//{
// memo[1]=1;
// memo[2]=2;
// if(memo[a]!=0)
// {
// return memo[a];
// }
// if(memo[a]==0)
// {
// memo[a]=f(a-1)%100000007+f(a-2)%100000007;
// return memo[a]%100000007;
// }
//}
//int main()
//{
// int n;
// scanf("%d",&n);
// if(n==1||n==2)
// {
// printf("%d",n);
// return ;
// }
// printf("%d",f(n)%100000007);
//}
//#include<stdio.h>
//int memo[10000]={};
//int f(int a)
//{
// memo[3]=2;
// if(memo[a]!=0)
// {
// return memo[a];
// }
// else
// {
// return memo[a]=f(a-3)*2%100000007;
// }
//}
//int main()
//{
// int n;
// scanf("%d",&n);
// if(n%3!=0)
// {
// printf("0");
// return ;
// }
// printf("%d",f(n));
//}
//#include<stdio.h>
//int memo[100001]={};
//int f(int a)
//{
// int i;
// memo[1]=1;
// memo[2]=3;
// memo[3]=5;
// if(memo[a]!=2&&memo[a]!=1)
// {
// return memo[a];
// }
// for(i=a-1;i>0;i--)
// {
// memo[a]=memo[a]%100007+f(i)%100007;
// }
// return memo[a];
//}
//int main()
//{
// int n;
// for(int i=1;i<=10000;i++)
// {
// if(i%2==0)
// {
// memo[i]=memo[i]+2;
// }
// else
// {
// memo[i]=memo[i]+1;
// }
// }
// scanf("%d",&n);
// printf("%d",f(n));
//}
#include<stdio.h>
int main()
{
}