<p>An attendance record for a student can be represented as a string where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters:</p>

<ul>
	<li><code>&#39;A&#39;</code>: Absent.</li>
	<li><code>&#39;L&#39;</code>: Late.</li>
	<li><code>&#39;P&#39;</code>: Present.</li>
</ul>

<p>Any student is eligible for an attendance award if they meet <strong>both</strong> of the following criteria:</p>

<ul>
	<li>The student was absent (<code>&#39;A&#39;</code>) for <strong>strictly</strong> fewer than 2 days <strong>total</strong>.</li>
	<li>The student was <strong>never</strong> late (<code>&#39;L&#39;</code>) for 3 or more <strong>consecutive</strong> days.</li>
</ul>

<p>Given an integer <code>n</code>, return <em>the <strong>number</strong> of possible attendance records of length</em> <code>n</code><em> that make a student eligible for an attendance award. The answer may be very large, so return it <strong>modulo</strong> </em><code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> 8
<strong>Explanation:</strong> There are 8 records with length 2 that are eligible for an award:
&quot;PP&quot;, &quot;AP&quot;, &quot;PA&quot;, &quot;LP&quot;, &quot;PL&quot;, &quot;AL&quot;, &quot;LA&quot;, &quot;LL&quot;
Only &quot;AA&quot; is not eligible because there are 2 absences (there need to be fewer than 2).
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 3
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 10101
<strong>Output:</strong> 183236316
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
public:
    int checkRecord(int n) {
        // return checkRecord_TopDown(n);
        // return checkRecord_BottomUp(n);
        // return checkRecord_BottomUp2(n);
        // return checkRecord_TransformMatrix(n);
        // return checkRecord_Combinatorics(n);
        return checkRecord_Trick(n);
    }

    int checkRecord_TopDown(int n) {
        // memo[len][absences][lates] := 
        //  #(valid strings we can further generate) of length len, given absences and lates now
        // -1 to indicate unsolved, NOT be 0 because it CAN NOT be distinguished from %MOD (which can be 0)
        vector<vector<vector<int>>> memo(n + 1, vector<vector<int>>(2, vector<int>(3, -1)));
        // for (int absences = 0; absences < 2; absences++)
        // for (int lates = 0; lates < 3; lates++)
        //     memo[0][absences][lates] = 1;
        return solve(n, 0, 0, memo);
    }

    int solve(int len, int absences, int lates, vector<vector<vector<int>>>& memo) {
        if (absences > 1 || lates > 2) return 0;
        if (len == 0) return 1;
        if (memo[len][absences][lates] != -1) {
            return memo[len][absences][lates];
        }
        int count = 0;
        // P
        count = (count + solve(len - 1, absences, 0, memo)) % MOD;
        // A
        count = (count + solve(len - 1, absences + 1, 0, memo)) % MOD;
        // L
        count = (count + solve(len - 1, absences, lates + 1, memo)) % MOD;
        return memo[len][absences][lates] = count;
    }

    int checkRecord_BottomUp(int n) {
        // dp[len][absences][lates] := 
        //  #(valid strings we could have generated) of length len containing absences and lates
        int kMOD = 1000000007;
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(3, 0)));
        dp[0][0][0] = 1;
        for (int len = 0; len < n; len++)
        for (int absences = 0; absences < 2; absences++)
        for (int lates = 0; lates < 3; lates++) {
            // P
            dp[len + 1][absences][0] = 
                (dp[len + 1][absences][0] + dp[len][absences][lates]) % MOD;
            // A
            if (absences < 1) {
                dp[len + 1][absences + 1][0] = 
                    (dp[len + 1][absences + 1][0] + dp[len][absences][lates]) % MOD;
            }
            // L
            if (lates < 2) {
                dp[len + 1][absences][lates + 1] = 
                    (dp[len + 1][absences][lates + 1] + dp[len][absences][lates]) % MOD;
            }
        }
        return accumulate(dp[n].begin(), dp[n].end(), 0, [&kMOD](long accu, auto& v) -> int {
            return (accu + accumulate(v.begin(), v.end(), 0L)) % kMOD;
        });
    }

    int checkRecord_BottomUp2(int n) {
        // dp[absences][lates] := 
        //  #(valid strings we could have generated) up to current length containing absences and lates
        int kMOD = 1000000007;
        vector<vector<int>> curr_dp(2, vector<int>(3, 0)), next_dp;
        curr_dp[0][0] = 1;
        for (int len = 0; len < n; len++) {
            // NOTE: outside of the loop of absences and lates!!!
            next_dp.assign(2, vector<int>(3, 0));

            for (int absences = 0; absences < 2; absences++)
            for (int lates = 0; lates < 3; lates++) {
                // P
                next_dp[absences][0] = 
                    (next_dp[absences][0] + curr_dp[absences][lates]) % kMOD;
                // A
                if (absences < 1)
                    next_dp[absences + 1][0] = 
                        (next_dp[absences + 1][0] + curr_dp[absences][lates]) % kMOD;
                // L
                if (lates < 2)
                    next_dp[absences][lates + 1] = 
                        (next_dp[absences][lates + 1] + curr_dp[absences][lates]) % kMOD;
            }

            curr_dp = next_dp;  // NOTE: outside of the loop of absences and lates!!!
        }
        return accumulate(curr_dp.begin(), curr_dp.end(), 0, [&kMOD](long accu, auto& v) -> int {
            return (accu + accumulate(v.begin(), v.end(), 0L)) % kMOD;
        });
    }

    int checkRecord_TransformMatrix(int n) {
        /*  Referece: solutions/5208681

            P(S0)=S0, L(S0)=S1, A(S0)=S3
            P(S1)=S0, L(S1)=S2, A(S1)=S3
            P(S2)=S0, A(S2)=S3
            P(S3)=S3, L(S3)=S4
            P(S4)=S3, L(S4)=S5
            P(S5)=S3

            const Matrix T = {
                //S0 S1 S2 S3 S4 S5
                {1, 1, 0, 1, 0, 0}, // S0
                {1, 0, 1, 1, 0, 0}, // S1
                {1, 0, 0, 1, 0, 0}, // S2
                {0, 0, 0, 1, 1, 0}, // S3
                {0, 0, 0, 1, 0, 1}, // S4
                {0, 0, 0, 1, 0, 0}  // S5
            };

            Define:
              T[Si][Sj] := #(valid strings) of paths to get to State Sj from Si with 1 step
            then:
            T^n[Si][Sj] := #(valid strings) of paths to get to State Sj from Si with n steps
          
            Because:
            #(valid strings) of paths to get to State Sj from Si with (a+b) steps = 
                Sum over all k of Sum over all paths from (Si - a steps -> Sk - b steps -> Sj)

            T^(a+b)[Si][Sj] = Sum_k{ T^a[Si][Sk] * T^b[Sk][Sj] }    0 <= k <= 5
        */
        vector<vector<int>> T = {
            //S0 S1 S2 S3 S4 S5
            {1, 1, 0, 1, 0, 0}, // S0
            {1, 0, 1, 1, 0, 0}, // S1
            {1, 0, 0, 1, 0, 0}, // S2
            {0, 0, 0, 1, 1, 0}, // S3
            {0, 0, 0, 1, 0, 1}, // S4
            {0, 0, 0, 1, 0, 0}  // S5
        };

        T = matPow(T, n);
        return accumulate(T[0].begin(), T[0].end(), 0L) % MOD;
    }

    vector<vector<int>> matPow(const vector<vector<int>>& A, int p) {
        if (p == 1) return A;
        return move(p % 2 ? matMul(matPow(A, p - 1), A) : matPow(matMul(A, A), p / 2));
    }

    vector<vector<int>> matMul(const vector<vector<int>>& A, const vector<vector<int>>& B) {
        int m = A.size(), n = m > 0 ? A[0].size() : 0;
        int p = B.size(), q = p > 0 ? B[0].size() : 0;
        if (m * n * p * q == 0 || n != q) throw;
        vector<vector<int>> C(m, vector<int>(q, 0));
        for (int i = 0; i < m; i++)
        for (int j = 0; j < q; j++)
        for (int k = 0; k < n; k++)
            C[i][j] = (C[i][j] + 1L * A[i][k] * B[k][j]) % MOD;
        return move(C);
    }

    int checkRecord_Combinatorics(int n) {
        // g(n) := number of valid strings of length n, only composed of 'P' and 'L'
        // f(n) := number of valid strings of length n, only composed of 'P', 'A' and 'L'
        // f(n) = g(n) + sum_i{ g(i) * g(n - 1 - i) }    0 <= i <= n - 1
        //
        // g(n) = g(n - 1) + g(n - 2) + g(n - 3)
        // g(n) = g(n + 3) - g(n + 2) - g(n + 1)
        // g(0) = 1, g(1) = 2, g(2) = 4, g(3) = 7, g(4) = 13 ...

        vector<int> g(max(3, n + 1), 0);
        g[0] = 1;
        g[1] = 2;
        g[2] = 4;
        for (int i = 3; i <= n; i++)
            g[i] = (0L + g[i - 1] + g[i - 2] + g[i - 3]) % MOD;

        int ans = g[n];
        for (int i = 0; i < n; i++)
            ans = (ans + 1L * g[i] * g[n - 1 - i]) % MOD;
        return ans;
    }

    int checkRecord_Trick(int n) {
        /*
            res[0] ---> the number of answer which includes 'A' , not ending with 'L'
            res[1] ---> the number of answer which includes 'A', ending with one 'L'
            res[2] ---> the number of answer which includes 'A', ending with two 'L'
            res[3] ---> the number of answer which don't include 'A' , not ending with 'L'
            res[4] ---> the number of answer which don't include 'A' , ending with one 'L'
            res[5] ---> the number of answer which don't include 'A' , ending with two 'L'
        */

        vector<int> res = {1, 0, 0, 1, 1, 0};  // 'A', 'P', 'L'
        for (int i = 1; i < n; i++) {
            vector<int> temp(6, 0);
            temp[0] = accumulate(res.begin(), res.end(), 0L) % MOD;  // 'P' for 0/1/2, 'A' for 3/4/5
            temp[1] = res[0] % MOD;  // 'L'
            temp[2] = res[1] % MOD;  // 'L'
            temp[3] = (0L + res[3] + res[4] + res[5]) % MOD;  // 'P'
            temp[4] = res[3] % MOD;  // 'L'
            temp[5] = res[4] % MOD;  // 'L'
            res = temp;
        }
        return accumulate(res.begin(), res.end(), 0L) % MOD;
    }

private:
    int MOD = 1000000007;
};
126640