AJJak-T003: Tiling-03

#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[0] = 1;
    dp1[1] = 1;
    for(int i = 1; i <= n; ++i){
        dp1[i] = ((lli)dp1[i - 1] + dp1[i - 2] + 2 * (lli)dp2[i - 1]) % MD;
        dp2[i] = ((lli)dp1[i - 2] + dp2[i - 1]) % MD;
    }
    cout << dp1[n];

    return 0;
}