class Solution(object):
    def checkRecord(self, n):
        """
        :type n: int
        :rtype: int
        """
        A=[0 for i in range(n+1)]
        P = [0 for i in range(n+1)]
        L = [0 for i in range(n+1)]
        P1 = [0 for i in range(n+1)]
        L1 = [0 for i in range(n+1)]
        A[0],P[0],L[0],P1[0],L1[0]=1,1,1,1,1
        A[1], P[1], L[1], P1[1], L1[1] = 2, 3, 3, 2, 2
        for i in range(2,n):
            L1[i]=(P1[i-1]+P1[i-2])% 1000000007
            P1[i]=(P1[i-1]+L1[i-1])% 1000000007
            A[i]=(P1[i-1]+L1[i-1])% 1000000007
            P[i]=(P[i-1]+L[i-1]+A[i-1])% 1000000007
            L[i]=(P[i-1]+A[i-1]+P[i-2]+A[i-2])% 1000000007
        ans=(A[n-1]+P[n-1]+L[n-1])% 1000000007
        return ans
n=1
s=Solution()
print(s.checkRecord(n))
"""
A[i] 表示字符串以A结尾的数量
对于P而言没有什么限制
P[i]=P[i-1]+A[i-1]+L[i-1]
对L而言不能有三个连续的L，如果没有限制：
L[i]=P[i-1]+A[i-1]+L[i-1]=P[i-1]+A[i-1]+P[i-2]+A[i-2]+L[i-2]
这里将L[i-2]删除，这里的L[i-2]代表了连续三个L
P[i-1]+A[i-1]+P[i-2]+A[i-2]
对于A而言，不能之前出现过A
定义P1[i]表示以P结尾 之前没有出现过A，L1[i]表示以L结尾 没有出现过A
A[i]=P1[i-1]+L1[i-1]
P1[i]=P1[i-1]+L1[i-1]
L1[i]=P1[i-1]+L1[i-1]=P1[i-1]+L1[i-1]+P1[i-2]+L1[i-2]
这里要去掉L1[i-2]
L1[i]=P1[i-1]+P1[i-2]
"""
DP大法

"""
class Solution:
    def checkRecord(self, n):
        
        :type n: int
        :rtype: int
        x: number of ways does not include A
        y: number of ways include A
        consider following stituation:
        xxxP: x[i-1]+y[i-1]
        xxxA: x[i-1]
        xxPL: x[i-2]+y[i-2]
        xxAL: x[i-2]
        xPLL: x[i-3]+y[i-3]
        xALL: x[i-3]
        
        x[i] = x[i-1]+x[i-2]+x[i-3]
        y[i] = y[i-1]+x[i-1]+y[i-2]+x[i-2]+y[i-3]+x[i-3]
        
        if n == 1:
            return 3
        x1,x2,x3 = 1,2,4
        y1,y2,y3 = 0,1,4
        for i in range(3,n+1):
            t = y3
            y3 = (x1+x2+x3+y1+y2+y3)%(10**9+7)
            y1 = y2
            y2 = t
            t = x3
            x3 = (x1+x2+x3)%(10**9+7)
            x1 = x2
            x2 = t
        return (x3+y3)%(10**9+7)
"""
