/*
#include<stdio.h>
int check[1000000];
int f(int k)
{
if(k<=3)
return check[k] = k;
if(check[k] != 0) return check[k];
return check[k] = (f(k-1)%100000007+f(k-2)%100000007)%100000007;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
*/
/*
#include<stdio.h>
int check[1000000];
int f(int n)
{
if(check[n])
return check[n];
if(n<=2)
return 0;
else if(n==3)
return check[n]=2;
check[n]=2*f(n-3)%100000007;
return check[n];
}
int main(){
int n;
scanf("%d",&n);
printf("%d",f(n));
}
*/
#include<stdio.h>
long long int f(int k){
if()
}
int main(){
int n,r;
}