1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
int dp[100010][5][5];
int n;
void init()
{
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;
    for(int i=1;i<=1e5;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<3;k++){
                dp[i][j][0]=(dp[i][j][0]+dp[i-1][j][k])%MOD;
                if(j) dp[i][j][0]=(dp[i][j][0]+dp[i-1][j-1][k])%MOD;
                if(k) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k-1])%MOD;
            }
        }
    } 
}
int main()
{
    init();
    while(cin>>n){
        ll ans=0;
        for(int j=0;j<2;j++){
            for(int k=0;k<3;k++){
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX