#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
char in[100], out[100];
long long int n,A[5][5][100100];
long long int f(int a, int b, int c){
	if(a>2 or b > 3) return 0;
	if(c==n) return 1;
	if(A[a][b][c]) return A[a][b][c];
	return A[a][b][c]=(f(a+1,b+1,c+1) +f(a+1,0,c+1)+f(0,b+1,c+1))%1000000007;
}

int main(){
	for(int I=1;I<41;I++){
		sprintf(in,".%d.in",I);
	    freopen(in,"w",stdout);
		//scanf("%d",&n);
		n = I;
		printf("%d\n",n);
		for(int i=0;i<5;i++)for(int j = 0; j<5;j++) for(int k = 0 ; k < 100100;k++)A[i][j][k]=0;
		sprintf(out,".%d.out",I);
	    freopen(out,"w",stdout);
		printf("%lld",f(0,0,1));
	}
	
}