My Solution
\nclass Solution {\n public:\n  int colorTheGrid(const int m, const int n) {\n    constexpr int mod = 1000000007;\n    constexpr int range = 2;\n    constexpr i
```\nclass Solution {\n public:\n  int colorTheGrid(const int m, const int n) {\n    constexpr int mod = 1000000007;\n    constexpr int range = 2;\n    constexpr int color_mask = 0b11;\n    /**\n     * `0b00` stands for red\n     * `0b01` stands for green\n     * `0b10` stands for blue\n     * `0b11` is invalid\n     */\n    int layouts = 1 << (2 * m);\n    vector<int> valid_layouts;\n    for (int layout = 0; layout < layouts; ++layout) {\n      bool valid = true;\n      for (int i_color = 0; i_color < m; ++i_color) {\n        const int previous_color = i_color == 0 ? color_mask : (layout >> 2 * (i_color - 1)) & color_mask;\n        const int current_color = (layout >> 2 * i_color) & color_mask;\n        if (current_color == color_mask || previous_color == current_color) {\n          valid = false;\n          break;\n        }\n      }\n      if (valid) {\n        valid_layouts.emplace_back(layout);\n      }\n    }\n    \n    int n_valid_layouts = static_cast<int>(valid_layouts.size());\n    vector<int> compatibles[n_valid_layouts];\n    for (int i = 0; i < n_valid_layouts - 1; ++i) {\n      for (int j = i + 1; j < n_valid_layouts; ++j) {\n        const int xor_result = valid_layouts[i] ^ valid_layouts[j];\n        bool compatible = true;\n        for (int i_color = 0; i_color < m; ++i_color) {\n          const int item = (xor_result >> 2 * i_color) & color_mask;\n          if (item == 0) {\n            compatible = false;\n            break;\n          }\n        }\n        if (compatible) {\n          compatibles[i].emplace_back(j);\n          compatibles[j].emplace_back(i);\n        }\n      }\n    }\n    \n    int dp[range][n_valid_layouts];\n    memset(dp, 0, sizeof(dp));\n    int previous = 0;\n    int current = 1;\n    fill(dp[previous], dp[previous] + n_valid_layouts, 1);\n    for (int c = 1; c < n; ++c) {\n      for (int layout = 0; layout < n_valid_layouts; ++layout) {\n        for (const int previous_layout : compatibles[layout]) {\n          dp[current][layout] = (dp[current][layout] + dp[previous][previous_layout]) % mod;\n        }\n      }\n      \n      previous ^= 1;\n      current ^= 1;\n      memset(dp[current], 0, sizeof(dp[current]));\n    }\n    \n    int ret = 0;\n    for (const int item : dp[previous]) {\n      ret = (ret + item) % mod;\n    }\n    return ret;\n  }\n};\n```
[]