#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <int MOD>
struct Mint {
    static constexpr int norm(long x) {
        x %= MOD;
        if (x < 0) {
            x += MOD;
        }
        return int(x);
    }

    static constexpr Mint pow(Mint base, long exp) {
        Mint ans = 1;
        while (exp) {
            if (exp & 1) {
                ans *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return ans;
    }

    static constexpr int inv(int x) {
        int y = MOD, vx = 1, vy = 0;
        while (x) {
            int k = y / x;
            y %= x;
            vy -= k * vx;
            swap(x, y);
            swap(vx, vy);
        }
        assert(y == 1);
        if (vy < 0) {
            vy += MOD;
        }
        return vy;
    }

    int x;

    constexpr Mint() : x(0) {}
    constexpr Mint(long x) : x(norm(x)) {}

    static constexpr Mint from_unsafe(int x) {
        Mint m;
        m.x = x;
        return m;
    }

    friend istream& operator>>(istream& in, Mint& m) {
        long x;
        in >> x;
        m = x;
        return in;
    }
    friend ostream& operator<<(ostream& out, const Mint& m) {
        return out << m.x;
    }

    explicit operator int() const {
        return x;
    }
    explicit operator long() const {
        return x;
    }

    bool operator==(const Mint& m) const {
        return x == m.x;
    }
    bool operator!=(const Mint& m) const {
        return x != m.x;
    }

    Mint operator-() const {
        return !x ? 0 : Mint::from_unsafe(MOD - x);
    }
    Mint operator+() const {
        return *this;
    }

    Mint& operator++() {
        x++;
        if (x == MOD) {
            x = 0;
        }
        return *this;
    }
    Mint& operator--() {
        if (!x) {
            x = MOD - 1;
        } else {
            x--;
        }
        return *this;
    }

    Mint& operator+=(const Mint& m) {
        x += m.x;
        if (x >= MOD) {
            x -= MOD;
        }
        return *this;
    }
    Mint& operator-=(const Mint& m) {
        x -= m.x;
        if (x < 0) {
            x += MOD;
        }
        return *this;
    }

    Mint& operator*=(const Mint& m) {
        x = int((long(x) * m.x) % MOD);
        return *this;
    }
    Mint& operator/=(const Mint& m) {
        return *this *= m.inv();
    }
    Mint inv() const {
        return Mint::from_unsafe(Mint::inv(x));
    }

    friend Mint operator++(Mint& a, int) {
        return ++a;
    }
    friend Mint operator--(Mint& a, int) {
        return --a;
    }
    friend Mint operator+(Mint a, const Mint& b) {
        return a += b;
    }
    friend Mint operator-(Mint a, const Mint& b) {
        return a -= b;
    }
    friend Mint operator*(Mint a, const Mint& b) {
        return a *= b;
    }
    friend Mint operator/(Mint a, const Mint& b) {
        return a /= b;
    }
};

using mint = Mint<int(1e9 + 7)>;

template <size_t N, size_t M>
using Mat = array<array<mint, M>, N>;

template <size_t A, size_t B, size_t C>
Mat<A, C> operator*(Mat<A, B> a, Mat<B, C> b) {
    Mat<A, C> ans {};
    for (size_t i = 0; i < A; i++) {
        for (size_t j = 0; j < B; j++) {
            for (size_t k = 0; k < C; k++) {
                ans[i][k] += a[i][j] * b[j][k];
            }
        }
    }
    return ans;
}

template <typename T>
struct MulIdentity {};

template <>
struct MulIdentity<mint> {
    static constexpr mint value = 1;
};

template <size_t N>
struct MulIdentity<Mat<N, N>> {
    static constexpr Mat<N, N> value = ([]() -> Mat<N, N> {
        Mat<N, N> ans {};
        for (size_t i = 0; i < N; i++) {
            ans[i][i] = 1;
        }
        return ans;
    })();
};

template <typename T>
T bpow(T base, long exp) {
    T ans = MulIdentity<T>::value;
    while (exp) {
        if (exp & 1) {
            ans = ans * base;
        }
        base = base * base;
        exp >>= 1;
    }
    return ans;
}

void solve() {
    long n, m, kv;
    cin >> n >> m >> kv;
    if (kv < 2) {
        cout << 0 << endl;
        return;
    }
    mint ladders =
        bpow(bpow(mint((kv - 2) * (kv - 3) + 2 * (kv - 1) - 1), n - 1), m);
    mint base =
        kv * (Mat<1, 2> {{{1, 0}}} *
              bpow(Mat<2, 2> {{{0, kv - 1}, {1, kv - 2}}}, m - 1))[0][1];
    dbg(ladders, base);
    cout << ladders * base << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    int tcs;
    cin >> tcs;
    while (tcs--) {
        solve();
    }
}