1
class Solution {
2
  static int mod = (int) (1e9 + 7);
3

4
  public static int dfs(int n, ArrayList<ArrayList<Integer>> arr, int src, int dp[][]) {
5
    if (n == 0) {
6
      return 1;
7
    }
8
    if (dp[n][src] != -1) {
9
      return dp[n][src];
10
    }
11
    int val = 0;
12
    for (Integer ap : arr.get(src)) {
13
      val = (val % mod + dfs(n - 1, arr, ap, dp) % mod) % mod;
14
    }
15
    return dp[n][src] = val;
16
  }
17

18
  public static void val(ArrayList<String> arr, int color, int m, String s) {
19
    if (m == 0) {
20
      arr.add(s);
21
      return;
22
    }
23
    for (int i = 0; i < 3; i++) {
24
      if (color != i) val(arr, i, m - 1, s + i);
25
    }
26
  }
27

28
  public static boolean Match(String s, String s1) {
29
    for (int i = 0; i < s.length(); i++) {
30
      if (s.charAt(i) == s1.charAt(i)) {
31
        return false;
32
      }
33
    }
34
    return true;
35
  }
36

37
  public int colorTheGrid(int m, int n) {
38
    ArrayList<String> arr = new ArrayList<String>();
39
    for (int i = 0; i < 3; i++) {
40
      String s = "";
41
      val(arr, i, m - 1, s + i);
42
    }
43
    ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
44
    for (int i = 0; i < arr.size(); i++) {
45
      adj.add(new ArrayList<Integer>());
46
    }
47

48
    for (int i = 0; i < adj.size(); i++) {
49
      for (int j = 0; j < arr.size(); j++) {
50
        if (Match(arr.get(i), arr.get(j))) {
51
          adj.get(i).add(j);
52
        }
53
      }
54
    }
55
    int dp[][] = new int[n + 1][adj.size() + 1];
56
    for (int i = 0; i <= n; i++) {
57
      Arrays.fill(dp[i], -1);
58
    }
59
    int sum12 = 0;
60
    for (int i = 0; i < arr.size(); i++) {
61
      sum12 = (sum12 % mod + dfs(n - 1, adj, i, dp) % mod) % mod;
62
    }
63
    return sum12;
64
  }
65
}