1
class Solution {
2
 public:
3
  const int mod = 1e9 + 7;
4

5
  int add(int a, int b) {
6
    return (a % mod + b % mod) % mod;
7
  }
8

9
  int sub(int a, int b) {
10
    return (a % mod - b % mod + mod) % mod;
11
  }
12

13
  int mul(int a, int b) {
14
    return (a % mod * 1ll * b % mod) % mod;
15
  }
16

17
  int checkRecord(int n) {
18
    if (n == 1) return 3;
19

20
    vector<int> PorL(n + 1); /*for strings ending with 'P' or 'L' and no 'A' is present*/
21
    vector<int> P(n + 1);    /* for strings ending with 'P' and no 'A' is present */
22

23
    // for 0 length strings only 1 option can be there (base case)
24
    P[0] = 1, PorL[0] = 1;
25

26
    /*for 1 length strings*/
27
    P[1] = 1;    /*can end with 'P' only */
28
    PorL[1] = 2; /*can end with either 'P' or 'L' */
29

30
    /*for 2 length strings*/
31
    P[2] = PorL[1];               /*ending with 'P' so the previous string can end with 'P' or
32
                                     'L' */
33
    PorL[2] = P[2] + P[1] + P[0]; /*either current char can be 'P' or 'L' or
34
                                     last 2 chars can be 'L' i.e "LL" */
35

36
    for (int i = 3; i <= n; i++) {
37
      P[i] = PorL[i - 1] % mod;
38
      PorL[i] = add(P[i], add(P[i - 1], P[i - 2]));
39
    }
40

41
    int ans = PorL[n]; /*if we have no 'A'*/
42
    /*since we can have only 1 'A' lets try to insert at each position */
43
    for (int i = 1; i <= n; i++) {
44
      /*if we insert 'A' at ith position */
45
      int leftLength = i - 1;  /*the length of the string to the left of i*/
46
      int rightLength = n - i; /*the length of the string to the right of i*/
47
      ans = add(ans, mul(PorL[leftLength], PorL[rightLength]));
48
    }
49
    return ans;
50
  }
51
};