```
def checkRecord(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0: return 0
if n == 1: return 3
M = 1000000007
dp = [0 for j in range (3)]
tmp = [0 for j in range (3)]
dpsum = [0 for i in range(n)]
#First calculate only P and up to 2 L combinations
dp[0] = 1 #1 p
dp[1] = 1 #0p 1L
dp[2] = 0 # 2L not possible for initial value of only one character
dpsum[0] = sum(dp)
for i in range(1,n):
tmp[0] = (dp[0] + dp[1] + dp[2])%M
tmp[1] = dp[0]
tmp[2] = dp[1]
dp = tmp[:]
dpsum[i] = sum(dp)
retVal = (dpsum[-1])
retVal += 2 * (dpsum[n-2]) %M
for i in range(1, n-1):
#insert 'A' one-by-one at every location by breaking the
#original list into two and lookup and multiply the total
#combinations of the two broken lists from the dpsum list.
retVal += (dpsum[i-1] * dpsum[n-2-i])%M
return retVal%M
```