A rewardable sequence can only have 6 states :

Either has **Absence** in previous sequence, we define it as hasA[i], or **Not Absence**, we define it as withoutA[i].

By each case, we can only have 0, 1, 2 continuous **Late** at **the end of sequence**.

By defining this 6 states, now we can draw all possible transitions. Each time we have 3 options, P, L, or A. The transition relationship is shown as following figure. Notice each time we take a P or A, we immediately end our L continuous record and go back to hasA[0] or withoutA[0].

Now the implementation is simply the translation of the figure. I attached both my first O(n) space version and the second optimized O(1) space version by observing that the current state only depends on last moment.

The time complexity is O(n).

```
public class Solution {
public int checkRecord(int n) {
long M = 1000000007;
// with i L at the end (i = 0, 1, 2)
long[][] hasA = new long[3][2];
long[][] withoutA = new long[3][2];
hasA[0][0] = 1; // 'A'
withoutA[0][0] = 1; // 'P'
withoutA[1][0] = 1; // 'L'
for (int i = 2; i <= n; i++) {
// only possible with 'P'
withoutA[0][(i + 1) % 2] = (withoutA[0][i % 2] + withoutA[1][i % 2] + withoutA[2][i % 2]) % M;
for (int j = 1; j <= 2; j++) {
// possible with 'L'
withoutA[j][(i + 1) % 2] = withoutA[j - 1][i % 2];
}
// possible with 'A' or 'P'
hasA[0][(i + 1) % 2] = (withoutA[0][(i + 1) % 2] + hasA[0][i % 2] + hasA[1][i % 2] + hasA[2][i % 2]) % M;
for (int j = 1; j <= 2; j++) {
// possible with 'L'
hasA[j][(i + 1) % 2] = hasA[j - 1][i % 2];
}
}
long res = 0;
for (int k = 0; k < 3; k++) {
res = (res + hasA[k][(n + 1) % 2] + withoutA[k][(n + 1) % 2]) % M;
}
return (int) res;
}
public int checkRecord2(int n) {
if (n == 1) return 3;
// with i L at the end (i = 0, 1, 2)
int[][] hasA = new int[3][n + 1];
int[][] withoutA = new int[3][n + 1];
hasA[0][1] = 1; // 'A'
withoutA[0][1] = 1; // 'P'
withoutA[1][1] = 1; // 'L'
for (int i = 2; i <= n; i++) {
// only possible with 'P'
withoutA[0][i] = withoutA[0][i - 1] + withoutA[1][i - 1] + withoutA[2][i - 1];
for (int j = 1; j <= 2; j++) {
// possible with 'L'
withoutA[j][i] = withoutA[j - 1][i - 1];
}
// possible with 'A' or 'P'
hasA[0][i] = withoutA[0][i - 1] + withoutA[1][i - 1] + withoutA[2][i - 1] + hasA[0][i - 1] + hasA[1][i - 1] + hasA[2][i - 1];
for (int j = 1; j <= 2; j++) {
// possible with 'L'
hasA[j][i] = hasA[j - 1][i - 1];
}
}
int res = 0;
for (int k = 0; k < 3; k++) {
res += hasA[k][n] + withoutA[k][n];
}
return res;
}
}
```