C++ bitmask DP
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 {\npublic:\n    int colorTheGrid(int m, int n) {\n        const long long mod = 1e9+7;\n        vector<Mask> masks(1);\n        for(int i=0;i<m;i++){\n            vector<Mask> new_masks;\n            for(auto mask:masks){\n                for(int c=1;c<4;c++){\n                    auto new_mask = mask;\n                    new_mask.set_color(i, c);\n                    if(new_mask.is_valid())\n                        new_masks.push_back(new_mask);\n                }\n            }\n            masks = move(new_masks);\n        }\n        const int size = masks.size();\n        vector v(size, 1LL);\n        while(--n){\n            vector new_v(size, 0LL);\n            for(int i=0;i<size;i++){\n                for(int j=0;j<size;j++){\n                    if(masks[i].can_be_neighbor(masks[j]))\n                        new_v[j] = (new_v[j] + v[i]) % mod;\n                }\n            }\n            v = move(new_v);\n        }\n        return accumulate(v.begin(), v.end(), 0LL) % mod;\n    }\n\n    struct Mask{\n        int get_color(int pos) const{\n            return (bits >> (pos*2)) & 3;\n        } \n        void set_color(int pos, int color){\n            bits |= (color << (pos*2));\n            size = max(size, 1+pos);\n        }\n\n        bool can_be_neighbor(Mask rhs) const{\n            for(int pos=0; pos<size; pos++){\n                if(get_color(pos) == rhs.get_color(pos))\n                    return false;\n            }\n            return true;\n        }\n\n        bool is_valid() const{\n            for(int i=1;i<size;i++){\n                if(get_color(i-1) == get_color(i))\n                    return false;\n            }\n            return true;\n        }\n\n        int print() const{\n            int x = 0;\n            for(int i=0;i<size;i++){\n                x*=10;\n                x += get_color(i);\n            }\n            return x;\n        }\n\n    private:\n        int size = 0;\n        int bits = 0;\n    };\n};\n```
['C++']