C++ Solution Using Binary Exponentiation On Matrix O(n^3 * log(m))
First we generate valid sequences with length N (N <= 5) (no adjacent cells have same color, ex:[1, 2, 3, 1, 3])\nWith the sequences, we can build an adjacency 
First we generate valid sequences with length N (N <= 5) (no adjacent cells have same color, ex:[1, 2, 3, 1, 3])\nWith the sequences, we can build an adjacency matrix.\nFor example, [1, 2, 3, 2, 1] can move to [2, 1, 2, 1, 3] because\n[1, 2, 3, 2, 1]\n[2, 1, 2, 1, 3]\nno adjacent cells have the same color\n[1, 3, 2, 1, 3] cannot move to [3, 1, 2, 1, 3] because\n[1, 3, **2**, 1, 3]\n[3, 1, **2**, 1, 3]\nWe can calculate the possible ways of length M with the adjacency matrix using the technique "Binary Exponentiation".\nTime Complexity : O(N^3 * log(M)) \n(Solvable with M <= 10^18)\n```\nconst int mod = 1e9 + 7;\n\ntypedef uint64_t ull;\n\nstruct Matrix {\n    vector<vector<ull>> M;\n    int N;\n    Matrix(int n) {\n        N = n;\n        M = vector<vector<ull>>(n, vector<ull>(n));\n    }\n    Matrix operator*(const Matrix& other) { //overload matrix multiplication with mod\n        Matrix ans(N);\n        for(int i = 0; i < N; ++i)\n            for(int j = 0; j < N; ++j)\n                for(int k = 0; k < N; ++k)\n                    ans.M[i][k] = (ans.M[i][k] + M[i][j] * other.M[j][k]) % mod;\n        return ans;\n    }\n};\n\nMatrix FastPower(Matrix a, ull b) { //fast matrix exponentiation\n    Matrix ans(a.N);\n    for(int i = 0; i < a.N; ++i)\n        ans.M[i][i] = 1;\n    while(b) {\n        if(b & 1)\n            ans = ans * a;\n        a = a * a;\n        b >>= 1;\n    }\n    return ans;\n}\n\nbool check(vector<int> a, vector<int> b) { //check if sequence A can move to sequence B\n    for(int i = 0; i < a.size(); ++i)\n        if(a[i] == b[i])\n            return 0;\n    return 1;\n}\n\nset<vector<int>> s; //store sequences from the below dfs\n\nvoid dfs(vector<int> v, int n) { //generate all sequences\n    if(v.size() == n) {\n        s.insert(v);\n        return;\n    }\n    v.push_back(0);\n    for(int i = 1; i <= 3; ++i) { //use 123 for color red green blue\n        v.back() = i;\n        dfs(v, n);\n    }\n    return;\n}\n\nclass Solution {\npublic:\n    int colorTheGrid(int n, int m) {    //n <= 5\n\t    s.clear();\n        dfs(vector<int>(0), n);\n        vector<vector<int>> valid; //store valid sequences\n        for(auto v : s) { //filter valid sequences\n            if(v.size() != n)\n                continue;\n            bool ok = 1;\n            for(int i = 1; i < n; ++i) {\n                if(v[i - 1] == v[i]) {\n                    ok = 0;\n                    break;\n                }\n            }\n            if(ok)\n                valid.push_back(v);\n        }\n        Matrix A(valid.size());\n        for(int i = 0; i < valid.size(); ++i) {\n            for(int j = 0; j < valid.size(); ++j) {\n                if(check(valid[i], valid[j])) //if sequence i can move to sequence j\n                    A.M[i][j] = 1; //add an edge from sequence i to j\n            }\n        }        \n        A = FastPower(A, m - 1);\n        ull ans = 0;\n        for(int i = 0; i < valid.size(); ++i)\n            for(int j = 0; j < valid.size(); ++j)\n                ans += A.M[i][j];\n        return ans % mod;\n    }\n};\n```\nPlease consider upvote if it helps ^^
['C', 'Matrix']