#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
const int N = 1e6 + 10, mod = 7 + 1e9;
const ll oo = 1e9, ooo = 1e9;
double eps = 1e-9;
ll n, dp[1001][1001][2][2][2][2][2];
ll cal(int i, int o, bool e, int p1, int p2, int p3, int p4){
if(i == n){
return o == 0 && e;
}
ll &dp = ::dp[i][o][e][p1][p2][p3][p4];
if(~dp)
return dp;
bool ex = p1 == 1 && p2 == 1 && p3 == 1 && p4 == 0;
dp = cal(i+1, o+1, e, p2, p3, p4, 1);
if(o > 0)
dp += cal(i+1, o-1, ex || e, p2, p3, p4, 0);
return dp % mod;
}
void realityisoftendisappointing(){
cin >> n;
memset(dp, -1, sizeof dp);
cout << cal(0, 0, 0, 0, 0, 0, 0);// the pattern starts with 1 so it's ok
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int t = 1;
// cin >> t;
while (t--)
realityisoftendisappointing();
}
Copy