1
// transform any decimal number to its ternary representation
2
let ternary = (num, len) => {
3
  let A = [],
4
    times = 0;
5
  while (times++ < len) A.push(num % 3), (num = (num - (num % 3)) / 3);
6
  return A;
7
};
8
// deduce whether my array does not contain 2 consecutive elements
9
let adjdiff = (Array) => Array.every((d, i) => i == 0 || d !== Array[i - 1]);
10
//main
11
var colorTheGrid = function (n, m) {
12
  let mod = 1e9 + 7,
13
    adj = [...Array(3 ** n)].map((d) => new Set()),
14
    //1.turn every potential state to a ternary(base3) representation
15
    base3 = [...Array(3 ** n)].map((d, i) => ternary(i, n)),
16
    //3 conditions such that state a can be previous to state b
17
    ok = (a, b) =>
18
      adjdiff(base3[a]) &&
19
      adjdiff(base3[b]) &&
20
      base3[a].every((d, i) => d !== base3[b][i]);
21
  //2.determine what are the acceptable adjacent states of any given state
22
  for (let m1 = 0; m1 < 3 ** n; m1++)
23
    for (let m2 = 0; m2 < 3 ** n; m2++)
24
      if (ok(m1, m2)) adj[m1].add(m2), adj[m2].add(m1);
25
  //3.do 2-row dp, where dp[state]= the number of colorings where the last line is colored based on state
26
  let dp = [...Array(3 ** n)].map((d, i) => Number(adjdiff(base3[i])));
27
  for (
28
    let i = 1, dp2 = [...Array(3 ** n)].map((d) => 0);
29
    i < m;
30
    i++, dp = [...dp2], dp2.fill(0)
31
  )
32
    for (let m1 = 0; m1 < 3 ** n; m1++)
33
      for (let prev of Array.from(adj[m1]))
34
        dp2[m1] = (dp2[m1] + dp[prev]) % mod;
35
  return dp.reduce((a, c) => (a + c) % mod, 0);
36
};