552. Student Attendance Record II

class Solution {
    public int checkRecord(int n) {
        int[][] dp = new int[2][3];
        dp[0][0] = 1;
        int MOD = 1_000_000_007;
        
        for (int i = 1; i <= n; i++) {
            // if P
            int[][] tmpDp = new int[2][3];
            
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 3; k++) {
                    tmpDp[j][0] = (tmpDp[j][0] + dp[j][k]) % MOD;
                }
            }
            // if A
            for (int k = 0; k < 3; k++) {
                tmpDp[1][0] = (tmpDp[1][0] + dp[0][k]) % MOD;
            }
            // if L
            for (int j = 0; j < 2; j++) {
                for (int k = 1; k < 3; k++) {
                    tmpDp[j][k] = (tmpDp[j][k] + dp[j][k - 1]) % MOD;
                }                
            }
            dp = tmpDp;
        }
        
        int res = 0;
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 3; k++) {
                res = (res + dp[j][k]) % MOD;
            }
        }
        return res;
    }
}