lc 1931

class Solution
{
    static const int MOD = 1000 * 1000 * 1000 + 7;
    vector<int> colors;
    void get_colors(int m, int s, vector<int> &v)
    {
        for (int i = 0; i < m; ++i) {
            v[i] = s % 3;
            s = s / 3;
        }
    }

  public:
    int colorTheGrid(int m, int n)
    {
        int state_space = pow(3, m);
        vector<vector<int>> dp(n + 1, vector<int>(state_space));
        colors = vector<int>(m);
        for (int i = 0; i < state_space; ++i) {
            get_colors(m, i, colors);
            bool avail = true;
            for (int j = 0; j < m - 1; ++j)
                if (colors[j] == colors[j + 1])
                    avail = false;
            if (avail)
                dp[0][i] = 1;
        }
        for (int i = 0; i < n - 1; ++i) {
            for (int j = 0; j < state_space; ++j) {
                if (dp[i][j] == 0)
                    continue;
                get_colors(m, j, colors);
                vector<int> nc(m);
                for (int k = 0; k < state_space; ++k) {
                    get_colors(m, k, nc);
                    bool ne = (nc != colors);
                    bool state_legal = true;
                    for (int r = 0; r < m; ++r) {
                        if (nc[r] == nc[r + 1])
                            state_legal == false;
                    }
                    if (k == 8) {
                        for (int r = 0; r < m; ++r) {
                            printf("nc[%d]:%d\n", r, nc[r]);
                        }
                        printf("state_legal:%d\n", int(state_legal));
                    }
                    if (ne && state_legal) {
                        printf("from state:%d to %d\n", j, k);
                        dp[i + 1][k] = (dp[i + 1][k] + dp[i][j]) % MOD;
                    }
                }
            }
        }
        int ret = 0;
        for (int i = 0; i < state_space; ++i) {
            ret = (ret + dp[n - 1][i]) % MOD;
        }
        return ret;
    }
};