AJJak-T005: Tiling-04

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 1000 + 5;
const int MD = 1e9 + 7;

int dp1[N], dp2[N];

int main(){

    int n;
    scanf("%d", &n);
    dp1[1] = 1;
    dp2[1] = 1;
    for(int i = 2; i <= n; ++i){
        dp1[i] = (4 * (lli)dp1[i - 1] + dp2[i - 1]) % MD;
        dp2[i] = (2 * (lli)dp2[i - 1] + dp1[i - 1]) % MD;
    }
    cout << (dp1[n] + dp2[n]) % MD;

    return 0;
}