class Solution {
public:
    int dp[1001][1001] = {};
    int M = 1e9+7;
    int N;
    int numTilings(int n) {
        N = n;
        return dfs(0,0);
    }
    long long dfs(int t, int b) {
        if(t > N || b > N){
            return 0;
        }
        if(t == N && b == N){
            return 1;
        }
        if(dp[t][b])
            return dp[t][b];
        long long res = 0; 
        if(t == b)
            res += dfs(t + 1, b + 1) + dfs(t + 2, b + 1) + dfs(t + 1, b + 2) + dfs(t + 2, b);
        else if(t + 1 == b)
            res += dfs(t + 2, b) + dfs(t + 2, b + 1);
        else if(t == b + 1)
            res += dfs(t, b + 2) + dfs(t + 1, b + 2);
        else if (t == b + 2)
            res += dfs(t, b + 2);
        return dp[t][b] = res % M;
    }
};