class Solution {

public:

const int MOD = 1e9 + 7;

int numTilings(int n) {

if (n == 0) return 1;

if (n == 1) return 1;

if (n == 2) return 2;

vector<long long> dp(n+1), prefix(n+1);

dp[0] = 1;

dp[1] = 1;

dp[2] = 2;

prefix[0] = 1;

prefix[1] = 2;

prefix[2] = 4;

for (int i = 3; i <= n; ++i) {

dp[i] = (dp[i-1] + dp[i-2] + 2 * prefix[i-3]) % MOD;

prefix[i] = (prefix[i-1] + dp[i]) % MOD;

}

return dp[n];

}

};