Let `noA[i+1]`

be the number of rewardable no `'A'`

records with length `i`

, then a rewardable no `'A'`

record could only end with `'P'`

, `'PL'`

or `'PLL'`

. So we have

```
noA[i+1] = noA[i] + noA[i-1] + noA[i-2].
```

Padding a rewardable no `'A'`

record with proper length to left and right of an `'A'`

will give a rewardable with `'A'`

record.

```
def checkRecord(self, n):
if n < 3: return 1 if n == 0 else (3 if n == 1 else 8)
noA = [1, 1, 2]
while (len(noA) < n+3): noA.append(sum(noA[-3:])%1000000007)
return (sum((noA[i+1]*noA[n-i]) for i in range(n+1)))%1000000007
```