include

include

include

using namespace std;

const int md = 1000000007;

// Function to add two vectors element-wise vector add(vector a, vector b) { int n = a.size(); int m = b.size(); int k = (n > m ? n : m); vector c(k); for (int i = 0; i < k; i++) { if (i >= n) c[i] = b[i]; else if (i >= m) c[i] = a[i]; else c[i] = (a[i] + b[i]) % md; } return c; }

// Function to multiply a vector by a constant vector mul(vector a, int b) { int n = a.size(); for (int i = 0; i < n; i++) { a[i] = ((long long)a[i] * b) % md; if (a[i] < 0) a[i] += md; } return a; }

// Function to multiply a vector by (x - bb) vector mul_x(vector a, int bb) { vector b(1, 0); b.insert(b.end(), a.begin(), a.end()); vector c = mul(a, -bb); return add(b, c); }

// Evaluate a polynomial represented by a vector for a given x int eval(vector a, int x) { int ans = 0, y = 1; for (int i = 0; i < (int)a.size(); i++) { ans = (ans + (long long)y * a[i]) % md; y = (long long)y * x % md; } return ans; }

// Normalize the vector by assigning consecutive numbers to non-zero elements void normalize(vector &a) { int n = a.size(); vector color(n + 3, 0); int last = 0; for (int i = 0; i < n; i++) { if (a[i] == 0) { continue; } if (color[a[i]] == 0) { color[a[i]] = ++last; } a[i] = color[a[i]]; } }

map, vector> f[10][10]; // Map to store intermediate results map, vector>::iterator it; vector result[10][10]; // Stores final results

int main() { // Pre-computation for (int rows = 1; rows <= 8; rows++) { for (int i = 0; i < rows; i++) for (int j = 0; j <= 8; j++) f[i][j].clear();

    vector<int> temp(rows, 0);
    f[0][0][temp] = vector<int>(1, 1);

    for (int col = 0; col < 8; col++) {
        for (int row = 0; row < rows; row++) {
            int n_col = col;
            int n_row = row;
            if (n_row + 1 < rows) {
                n_row++;
            } else {
                n_row = 0;
                n_col++;
            }

            it = f[row][col].begin();
            while (it != f[row][col].end()) {
                vector<int> state = (*it).first;
                vector<int> poly = (*it).second;
                int maxc = 0;
                for (int i = 0; i < rows; i++)
                    if (state[i] > maxc)
                        maxc = state[i];

                for (int c = 1; c <= maxc; c++) {
                    if (c == state[row]) {
                        continue;
                    }
                    if (row > 0 && c == state[row - 1]) {
                        continue;
                    }
                    vector<int> new_state = state;
                    new_state[row] = c;
                    normalize(new_state);
                    f[n_row][n_col][new_state] = add(f[n_row][n_col][new_state], poly);
                }

                vector<int> new_state = state;
                new_state[row] = maxc + 1;
                normalize(new_state);
                vector<int> new_poly = mul_x(poly, maxc);
                f[n_row][n_col][new_state] = add(f[n_row][n_col][new_state], new_poly);

                it++;
            }
        }
    }

    for (int cols = 1; cols <= 8; cols++) {
        result[rows][cols] = vector<int>();
        it = f[0][cols].begin();
        while (it != f[0][cols].end()) {
            vector<int> poly = (*it).second;
            result[rows][cols] = add(result[rows][cols], poly);
            it++;
        }
    }
}

int tt;
scanf("%d", &tt);
while (tt--) {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    printf("%d\n", eval(result[n][m], k));
}

return 0;

}