```
public int checkRecord(int n) {
if (n == 1) {
return 3;
}
if (n == 2) {
return 8;
}
long[] dpPLP = new long[n+1]; // awarded count only with P or L, end with P
long[] dpPLL = new long[n+1]; // awarded count only with P or L, end with L
long[] dpP = new long[n+1]; // awarded count, ends with 'P'
long[] dpA = new long[n+1]; // awarded count, ends with 'A'
long[] dpL = new long[n+1]; // awarded count, ends with 'L'
dpPLP[0] = 0; dpPLL[0] = 0;
dpPLP[1] = 1; dpPLL[1] = 1;
dpPLP[2] = 2; dpPLL[2] = 2;
dpP[0] = 0; dpA[0] = 0; dpL[0] = 0;
dpP[1] = 1; dpA[1] = 1; dpL[1] = 1;
dpP[2] = 3; dpA[2] = 2; dpL[2] = 3;
for (int i = 3; i <= n; i++) {
dpPLP[i] = dpPLP[i-1] + dpPLL[i-1];
dpPLL[i] = dpPLP[i-1] + dpPLP[i-2];
dpP[i] = dpP[i-1] + dpA[i-1] + dpL[i-1]; // last one is 'P'
dpA[i] = dpPLP[i-1] + dpPLL[i-1];
dpL[i] = dpP[i-1] + dpA[i-1] + dpP[i-2] + dpA[i-2];
dpPLP[i] %= 1000000007;
dpPLL[i] %= 1000000007;
dpP[i] %= 1000000007;
dpA[i] %= 1000000007;
dpL[i] %= 1000000007;
}
return (int)((dpP[n] + dpA[n] + dpL[n]) % (long)1000000007);
}
```