//#include <stdio.h>
//#include <stdlib.h>
//
//int memo[100001]= {};
//
//int rec(int n)
//{
// if(n==1)
// return 1;
// if(n==2)
// return 2;
// if(n==3)
// return 3;
// if(n==4)
// return 5;
//
// if(memo[n]!=0)
// {
// return memo[n]%100000007;
// }
// else
// {
// memo[n]=rec(n-1)+rec(n-2);
// return memo[n]%100000007;
// }
//}
//
//int main()
//{
// int n;
//
// scanf("%d",&n);
//
// printf("%d", rec(n));
//
// return 0;
//}
//#include <stdio.h>
//
//int memo[10001]= {};
//
//int rec(int n)
//{
// if(n==3) return 2;
// if(n%3!=0)
// {
// return 0;
// }
// if(memo[n]!=0)
// {
// return memo[n]%100000007;
// }
// else
// {
// memo[n]=rec(n-3)+rec(n-3);
// return memo[n]%100000007;
// }
//}
//
//int main()
//{
// int n;
//
// scanf("%d", &n);
//
// printf("%d", rec(n));
//
// return 0;
//}
//#include <stdio.h>
//
//int memo[10001]= {};
//
//int rec(int n)
//{
// if(n==1)
// return 1;
// if(n==2)
// return 3;
// if(n==3)
// return 5;
// if(n==4)
// return 11;
//
// if(memo[n]!=0)
// {
// return memo[n]%100007;
// }
// else
// {
// memo[n]=rec(n-1)+rec(n-2)*2;
// return memo[n]%100007;
// }
//
//}
//
//int main()
//{
// int n;
//
// scanf("%d",&n);
//
//
// printf("%d",rec(n));
//
// return 0;
//}