Hi i share the code in C++ i could solve this like this:

include

using namespace std;

const long long mod = 1000000007; vector f(1111), g(1111), h(1111);

long long pow(long long a, int p) { long long ans = 1; while (p) { if (p % 2) ans = ans * a % mod; a = a * a % mod; p /= 2; } return ans; }

int legoBlocks(int n, int m) { // Initialize f with the number of ways to fill each width f[0] = 1; for (int i = 1; i <= 1000; i++) { f[i] = 0; for (int j = 1; j <= 4; j++) { if (i - j >= 0) f[i] = (f[i] + f[i - j]) % mod; } }

// Compute the number of ways to fill each row with width m
for (int i = 1; i <= m; i++) {
    g[i] = pow(f[i], n);
}

// Compute the number of valid walls
memset(h.data(), 0, h.size() * sizeof(h[0]));
h[0] = 1; // Base case for height 0
for (int i = 1; i <= m; i++) {
    h[i] = g[i];
    long long tmp = 0;
    for (int j = 1; j < i; j++) {
        tmp = (tmp + h[j] * g[i - j] % mod) % mod;
    }
    h[i] = (g[i] - tmp + mod) % mod;
}

return h[m];

}

string ltrim(const string &str) { string s(str); s.erase( s.begin(), find_if(s.begin(), s.end(), not1(ptr_fun(isspace))) ); return s; }

string rtrim(const string &str) { string s(str); s.erase( find_if(s.rbegin(), s.rend(), not1(ptr_fun(isspace))).base(), s.end() ); return s; }

vector split(const string &str) { vector tokens; string::size_type start = 0; string::size_type end = 0; while ((end = str.find(" ", start)) != string::npos) { tokens.push_back(str.substr(start, end - start)); start = end + 1; } tokens.push_back(str.substr(start)); return tokens; }

int main() { ofstream fout(getenv("OUTPUT_PATH"));

string t_temp;
getline(cin, t_temp);
int t = stoi(ltrim(rtrim(t_temp)));

for (int t_itr = 0; t_itr < t; t_itr++) {
    string first_multiple_input_temp;
    getline(cin, first_multiple_input_temp);
    vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));
    int n = stoi(first_multiple_input[0]);
    int m = stoi(first_multiple_input[1]);
    int result = legoBlocks(n, m);
    fout << result << "\n";
}

fout.close();
return 0;

}