package main

import (
	"bufio"
	"fmt"
	"os"
)

const MOD = 998244353
const MAXN = 1000005

var fact []int64
var invFact []int64
var V_pow []int64
var R_pow []int64

func power(base, exp int64) int64 {
	res := int64(1)
	base %= MOD
	if base < 0 {
		base += MOD
	}
	for exp > 0 {
		if exp%2 == 1 {
			res = (res * base) % MOD
		}
		base = (base * base) % MOD
		exp /= 2
	}
	return res
}

func modInverse(n int64) int64 {
	return power(n, MOD-2)
}

func precompute(maxN int) {
	fact = make([]int64, maxN+1)
	invFact = make([]int64, maxN+1)
	fact[0] = 1
	invFact[0] = 1
	for i := 1; i <= maxN; i++ {
		fact[i] = (fact[i-1] * int64(i)) % MOD
	}
	invFact[maxN] = modInverse(fact[maxN])
	for i := maxN - 1; i >= 1; i-- {
		invFact[i] = (invFact[i+1] * int64(i+1)) % MOD
	}
}

func nCr(n, r int) int64 {
	if r < 0 || r > n {
		return 0
	}
	return fact[n] * invFact[r] % MOD * invFact[n-r] % MOD
}

func main() {
	precompute(MAXN)
	V_pow = make([]int64, MAXN+1)
	R_pow = make([]int64, MAXN+1)

	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var t int
	if _, err := fmt.Fscan(reader, &t); err != nil {
		return
	}

	for tc := 0; tc < t; tc++ {
		var n, m, v int
		fmt.Fscan(reader, &n, &m, &v)

		v_m := power(int64(v), int64(m))
		v_nm := power(v_m, int64(n))

		if v == 1 {
			fmt.Fprintln(writer, v_nm)
			continue
		}

		false_matrices := int64(0)

		V_pow[0] = 1
		for i := 1; i <= n; i++ {
			V_pow[i] = (V_pow[i-1] * int64(v)) % MOD
		}

		for k := 1; k < v; k++ {
			term1_base := (power(int64(v), int64(n)) - power(int64(v-k), int64(n)) + MOD) % MOD
			term1 := power(term1_base, int64(m))

			term2_base := (v_m - power(int64(k), int64(m)) + MOD) % MOD
			term2 := power(term2_base, int64(n))

			H_kk := (term1 + term2 - v_nm) % MOD
			if H_kk < 0 {
				H_kk += MOD
			}

			H_k1_k := int64(0)
			R_base := int64(v - k + 1)
			
			R_pow[0] = 1
			for i := 1; i <= n; i++ {
				R_pow[i] = (R_pow[i-1] * R_base) % MOD
			}

			P_i := int64(1)
			for i := 0; i <= n; i++ {
				inner := (P_i * V_pow[n-i]) % MOD
				inner = (inner - R_pow[n-i]) % MOD
				if inner < 0 {
					inner += MOD
				}

				term := power(inner, int64(m))
				term = (term * nCr(n, i)) % MOD

				if i%2 == 1 {
					H_k1_k = (H_k1_k - term) % MOD
				} else {
					H_k1_k = (H_k1_k + term) % MOD
				}

				P_i = (P_i * int64(k)) % MOD
			}
			if H_k1_k < 0 {
				H_k1_k += MOD
			}

			G_k := (H_kk - H_k1_k) % MOD
			if G_k < 0 {
				G_k += MOD
			}

			false_matrices = (false_matrices + G_k) % MOD
		}

		ans := (v_nm - false_matrices) % MOD
		if ans < 0 {
			ans += MOD
		}

		fmt.Fprintln(writer, ans)
	}
}