class Solution {
public:
    // 状态定义：定义 dp[i][j] 表示对于 i*j 个地块总共有多少总放置方式
    // 状态方程：dp[i][j] = sum((j >= 2 ? dp[i][j-2] : dp[i-1][n-1]), (j >= 1 ?
    // dp[i][j-1] : dp[i-1][n-1])) <=> dp[i+1][j+2] = sum((j >= 2 ? dp[i+1][j] :
    // dp[i][n+1]), (j >= 1 ? dp[i+1][j+1] : dp[i][n+1]))
    static constexpr int MOD{1'000'000'000 + 7};
    int countHousePlacements(int n) {
        vector<vector<int>> memo(2 + 1, vector<int>(n + 2, 0));
        memo[1][0] = memo[1][1] = memo[0][n + 1] = 1;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < n; ++j) {
                if (j >= 2) {
                    memo[i + 1][j + 2] =
                        (memo[i + 1][j + 2] + memo[i + 1][j]) % MOD;
                } else {
                    memo[i + 1][j + 2] =
                        (memo[i + 1][j + 2] + memo[i][n + 1]) % MOD;
                }

                if (j >= 1) {
                    memo[i + 1][j + 2] =
                        (memo[i + 1][j + 2] + memo[i + 1][j + 1]) % MOD;
                } else {
                    memo[i + 1][j + 2] =
                        (memo[i + 1][j + 2] + memo[i][n + 1]) % MOD;
                }
            }
        }

        return memo[2][n + 1];
    }
};