1
vector<string> moves;
2
int MOD = 1e9 + 7;
3
void fill(string s, int n, int p) {
4
  if (n == 0) {
5
    moves.push_back(s);
6
    return;
7
  }
8
  for (int i = 1; i < 4; i++) {
9
    if (p == i) {
10
      continue;
11
    }
12
    string m = to_string(i);
13
    fill(s + m, n - 1, i);
14
  }
15
  return;
16
}
17
class Solution {
18
 public:
19
  vector<vector<int>> memo;
20
  int solve(int n, int lastIdx, int m) {
21
    if (n == 0) return 1;
22
    int ret = 0;
23
    if (memo[n][lastIdx] != -1) return memo[n][lastIdx];
24
    string last = moves[lastIdx];
25
    for (int idx = 0; idx < moves.size(); idx++) {
26
      string move = moves[idx];
27
      bool same = false;
28
      for (int i = 0; i < m; i++)
29
        if (move[i] == last[i]) same = true;
30
      if (!same) ret = (ret + solve(n - 1, idx, m) % MOD) % MOD;
31
    }
32
    return memo[n][lastIdx] = ret % MOD;
33
  }
34
  int colorTheGrid(int m, int n) {
35
    moves.clear();
36
    fill("", m, -1);
37
    // cout<<moves.size()<<endl;
38
    memo.resize(n + 1, vector<int>(moves.size(), -1));
39
    int ret = 0;
40
    for (int idx = 0; idx < moves.size(); idx++) ret = (ret + solve(n - 1, idx, m) % MOD) % MOD;
41
    return ret;
42
  }
43
};