Inspired by @zym_ustc to finish my algorithm.

Step 1. calculate the number of valid sequences without `A`

, which will end with `P`

, with `L`

and with `LL`

. The result is the sum of these three states.

Step 2. insert `A`

into the sequence, there are `n`

positions to put `A`

. Suppose we put `A`

at location `i`

, on the left side of `A`

, there are `i-1`

positions to fill without `A`

; on the right side of `A`

, there are `n-i`

positions to fill without `A`

. Here we reuse the results from step 1.

```
class Solution {
public:
int checkRecord(int n) {
if (n==1) return 3;
vector<int> endP(n+1,0), end1L(n+1,0), end2L(n+1,0), noA(n+1,1);
endP[1] = 1; end1L[1] = 1; end2L[1] = 0; noA[1] = 2;
for (int i=2; i<=n; i++){
endP[i] = add( add(endP[i-1],end1L[i-1]), end2L[i-1]);
end1L[i] = endP[i-1];
end2L[i] = end1L[i-1];
noA[i] = add( add(endP[i],end1L[i]), end2L[i]);
}
int withA = 0;
for (int i=1; i<=n; i++){
withA = add(withA, ((long long)noA[i-1]*noA[n-i])%1000000007);
}
return add(withA, noA[n]);
}
int add(int a, int b){
return (a%1000000007 + b%1000000007)%1000000007;
}
};
```