Java solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n  public int colorTheGrid(int m, int n) {\n    this.m = m;\n    this.n = n;\n    return dp(0, 0, 0, 0);\n  }\n\n  private static final int kMod = 1_000_000_007;\n  private int m;\n  private int n;\n  private int[][] memo = new int[1000][1024];\n\n  private int dp(int r, int c, int prevColMask, int currColMask) {\n    if (c == n)\n      return 1;\n    if (memo[c][prevColMask] != 0)\n      return memo[c][prevColMask];\n    if (r == m)\n      return dp(0, c + 1, currColMask, 0);\n\n    int ans = 0;\n\n    // 1 := red, 2 := green, 3 := blue\n    for (int color = 1; color <= 3; ++color) {\n      if (getColor(prevColMask, r) == color)\n        continue;\n      if (r > 0 && getColor(currColMask, r - 1) == color)\n        continue;\n      ans += dp(r + 1, c, prevColMask, setColor(currColMask, r, color));\n      ans %= kMod;\n    }\n\n    if (r == 0)\n      memo[c][prevColMask] = ans;\n\n    return ans;\n  }\n\n  // E.g. __ __ __ __ __\n  //      01 10 11 11 11\n  //      R  G  B  B  B\n  // GetColor(0110111111, 3) -> G\n  private int getColor(int mask, int r) {\n    return mask >> r * 2 & 3;\n  }\n\n  private int setColor(int mask, int r, int color) {\n    return mask | color << r * 2;\n  }\n}\n\n```
['Java']