1
class Solution {
2
  int mod = 1000000000 + 7;
3

4
  public int checkRecord(int n) {
5
    int[][][] cache = new int[n + 1][2][3];
6
    for (int i = 0; i <= n; i++) {
7
      for (int j = 0; j < 2; j++) {
8
        for (int k = 0; k < 3; k++) cache[i][j][k] = -1;
9
      }
10
    }
11
    return populate(n, 0, 1, 2, cache);
12
  }
13

14
  public int populate(int n, int ptr, int aCount, int lCount, int[][][] cache) {
15
    if (ptr >= n) return 1;
16
    if (cache[ptr][aCount][lCount] != -1) return cache[ptr][aCount][lCount];
17
    long count = 0;
18
    // Late
19
    if (lCount > 0) {
20
      count = populate(n, ptr + 1, aCount, lCount - 1, cache) % mod;
21
    }
22
    // Present
23
    count = (count + populate(n, ptr + 1, aCount, 2, cache)) % mod;
24
    // Absent
25
    if (aCount == 1) count = (count + populate(n, ptr + 1, aCount - 1, 2, cache)) % mod;
26
    cache[ptr][aCount][lCount] = (int) (count % mod);
27
    return cache[ptr][aCount][lCount];
28
  }
29
}