At time t where every report is length t, Let `a, b, c`

be sequence types *without* an 'A' ending in N, NL, LL; and `d,e,f`

be sequence types *with* an 'A' ending in N, NL, LL. (Here, N will denote a non-'L' character.) These types are disjoint, and exhaustive (their union is the set of all valid reports.) At the beginning when t = 1, `a = b = d = 1`

and we should compute N-1 more steps.

From a sequence of type a, b, c, we can write an 'A' to give us a sequence of type d, or a 'P' to give us a sequence of type a. From a sequence of type d, e, f, we can write a 'P' to give us a sequence of type d. From a sequence of type a, b, d, e, we can write an 'L' to give a sequence of (respectively) b, c, e, f. These are all the letters we could write in any situation. Working backwards, we can get the sums for `a,b,c,d,e,f`

written below.

```
def checkRecord(self, N):
MOD = 10**9 + 7
a = b = d = 1
c = e = f = 0
for _ in xrange(N-1):
a, b, c, d, e, f = (a+b+c)%MOD, a, b, (a+b+c+d+e+f)%MOD, d, e
return (a+b+c+d+e+f)%MOD
```