<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>

#include <bits/stdc++.h>

using namespace std;

class MOD_Int {
public:
    int val;
    MOD_Int(int v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;  // Ensure value is always non-negative
    }

    MOD_Int operator+=(const MOD_Int& other) {
        this->val = (val + other.val) % MOD;
        return *this;
    }
    MOD_Int operator+(const MOD_Int& other) const {
        MOD_Int result = *this;
        result += other;
        return result;
    }
    MOD_Int& operator=(const MOD_Int& other) {
        if (this != &other) {  // Prevent self-assignment
            this->val = other.val % MOD;
            if (this->val < 0) this->val += MOD;  // Ensure non-negative value
        }
        return *this;
    }

private:
    const int MOD = 1e9 + 7;
};

class Solution {
public:
    int checkRecord(int n) {
        vector<vector<MOD_Int>> previous(2, vector<MOD_Int>(3, MOD_Int(0)));
        previous[0][0] = MOD_Int(1);

        for (int i = 0; i < n; i++) {
            vector<vector<MOD_Int>> current(2, vector<MOD_Int>(3, 0));

            // Absent
            current[1][0] += previous[0][0] + previous[0][1] + previous[0][2];

            // Late
            current[0][1] += previous[0][0];

            current[0][2] += previous[0][1];

            current[1][1] += previous[1][0];

            current[1][2] += previous[1][1];

            // Present
            current[0][0] += previous[0][0] + previous[0][1] + previous[0][2];

            current[1][0] += previous[1][0] + previous[1][1] + previous[1][2];

            // update
            previous = std::move(current);
        }

        return (previous[0][0] + previous[0][1] + previous[0][2] + previous[1][0] + previous[1][1] + previous[1][2])
            .val;
    }
};
475278