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:


	'A': Absent.
	'L': Late.
	'P': Present.


Any student is eligible for an attendance award if they meet both of the following criteria:


	The student was absent ('A') for strictly fewer than 2 days total.
	The student was never late ('L') for 3 or more consecutive days.


Given an integer n, return the number of possible attendance records of length n that make a student eligible for an attendance award. The answer may be very large, so return it modulo 109 + 7.

&nbsp;
Example 1:

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


Example 2:

Input: n = 1
Output: 3


Example 3:

Input: n = 10101
Output: 183236316


&nbsp;
Constraints:


	1 &lt;= n &lt;= 105


class Solution:
    def checkRecord(self, n: int) -> int:
        if n == 1:
            return 3
        if n==2:
            return 8
        """
        Keep track of last 2 digits
        ways to get ll = last combinations ending with p,l (l,l not allowed)
        ways to get lp = last combinations ending with l,p + p,l
        and so on
        
        finally account for adding A by the usual loop.
        """
        
        combos_l_l = 1
        combos_l_p = 1
        combos_p_l = 1
        combos_p_p = 1

        MOD = 1000000007
        
        f = [0]*(n+1)
        f[0] = 1
        f[1] = 2
        f[2] = 4
        for i in range(2, n):
            combos_l_l_new = combos_p_l
            combos_l_p_new = combos_l_l + combos_p_l
            combos_p_l_new = combos_l_p + combos_p_p 
            combos_p_p_new = combos_l_p + combos_p_p
            
            combos_l_l, combos_l_p, combos_p_l, combos_p_p = combos_l_l_new%MOD, combos_l_p_new%MOD, combos_p_l_new%MOD, combos_p_p_new  %MOD
            
            f[i+1] = (combos_l_l + combos_l_p + combos_p_l + combos_p_p)%MOD
            

        total = f[-1]
        # print(f)
        for i in range(1,n+1):
            total += (f[i-1]*f[n-i]) 
            
        return ( total ) % (MOD)
            
class Solution {
    int mod=1000000000+7;
    public int checkRecord(int n) {
        int[][][] cache=new int[n+1][2][3];
        for(int i=0; i<=n; i++){
            for(int j=0; j<2; j++){
                for(int k=0; k<3; k++)cache[i][j][k]=-1;
            }
        }
        return populate(n, 0, 1, 2, cache);
    }
    public int populate(int n, int ptr, int aCount, int lCount, int[][][] cache){
        if(ptr>=n)return 1;
        if(cache[ptr][aCount][lCount]!=-1)return cache[ptr][aCount][lCount];
        long count=0;
        // Late
        if(lCount>0){
            count=populate(n, ptr+1, aCount, lCount-1, cache)%mod;
        }
        // Present
        count=(count+populate(n, ptr+1, aCount, 2, cache))%mod;
        // Absent
        if(aCount==1)count=(count+populate(n, ptr+1, aCount-1, 2, cache))%mod;
        cache[ptr][aCount][lCount]=(int)(count%mod);
        return cache[ptr][aCount][lCount];
    }
}
class Solution {
public:
    int mod = 1e9+7;
    int dp[100001][10][10];
    int recur(int abs,int late,int n){
        if(abs > 1){
            return 0;
        }
        if(late >= 3){
            return 0;
        }
        if(n == 0){
            return 1;
            
        }
        if(dp[n][late][abs] != -1) return dp[n][late][abs];
        
        int ans = 0;
        ans = (ans%mod + recur(abs+1,0,n-1)%mod)%mod;
        
        ans = (ans%mod + recur(abs,late+1,n-1)%mod)%mod;
        
        ans = (ans%mod + recur(abs,0,n-1)%mod)%mod;
       //This dp is running from n to 0 and is cut off if
        //absent is greater than 1 or late of consecutive is greater than
        //equal to 3.
        //Here in the first recursion i.e line 19 & line 23 late is made 0
        //to signify that the consecutive lates are stopped.***

        return dp[n][late][abs] = ans;
    }
    int checkRecord(int n) {
        for(int i=0;i<=100000;i++){
            for(int j=0;j<10;j++){
                for(int k=0;k<10;k++){
                    dp[i][j][k] = -1;
                }
            }
        }
        return recur(0,0,n);
    }
};
/**
 * @param {number} n
 * @return {number}
 */
var checkRecord = function(n) {
  /**
   * P(n) = A(n - 1) + P(n - 1) + L(n - 1), n ≥ 2.
   * L(n) = A(n - 1) + P(n - 1) + A(n - 2) + P(n - 2), n ≥ 3.
   * A(n) = A(n - 1) + A(n - 2) + A(n - 3), n ≥ 4.
   */
  const m = 1000000007;
  const P = Array(n);
  const A = Array(n);
  const L = Array(n);
  A[0] = 1;
  L[0] = 1;
  P[0] = 1;
  A[1] = 2;
  A[2] = 4;
  L[1] = 3;
  for (let i = 1; i < n; i++) {
    P[i] = (A[i - 1] + L[i - 1] + P[i - 1]) % m;
    if (i >= 3) A[i] = (A[i - 1] + A[i - 2] + A[i - 3]) % m;
    if (i >= 2) L[i] = (A[i - 1] + P[i - 1] + A[i - 2] + P[i - 2]) % m;
  }
  return (P[n - 1] + A[n - 1] + L[n - 1]) % m;
};
Student Attendance Record II