Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has a matrix $A$ with size $M \times N$. He wants to fill each of its cells with a random integer between $1$ and $K$ (inclusive); these integers are independent.

Then, Chef builds a directed graph on this matrix: for each ordered pair of side-adjacent cells of the matrix such that the value in the first cell is greater than or equal to the value in the second cell, he adds an edge from the first cell to the second cell.

Find the expected value of the number of strongly connected components (SCC) in this graph. It can be proved that the answer can be represented as a fraction $P/Q$, where $P$ and $Q$ are positive integers and $Q$ is coprime with $998,244,353$. You should compute $P \cdot Q^{-1}$ modulo $998,244,353$, where $Q^{-1}$ denotes the multiplicative inverse of $Q$ modulo $998,244,353$.

------  Input ------
The first and only line of the input contains three space-separated integers $M$, $N$ and $K$.

------  Output ------
Print a single line containing one integer $P \cdot Q^{-1}$ modulo $998,244,353$.

------  Constraints ------
$1 ≤ M ≤ 2$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ 10^{8}$

------  Subtasks ------
Subtask #1 (5 points, time limit 1s):
$N ≤ 4$
$K ≤ 5$ 

Subtask #2 (10 points, time limit 2s): $M = 1$

Subtask #3 (10 points, time limit 2s):
$M = 2$
$N ≤ 500$
$K ≤ 500$

Subtask #4 (75 points, time limit 3s): original constraints

----- Sample Input 1 ------ 
2 2 2
----- Sample Output 1 ------ 
873463811
----- explanation 1 ------ 
The total number of ways to fill the matrix is $16$. We get:
- $1$ SCC with a probability $2/16$
- $2$ SCCs with a probability $12/16$
- $3$ SCCs with a probability $0/16$
- $4$ SCCs with a probability $2/16$

The expected number of SCCs is $2/16 + 24/16 + 8/16 = 34/16 = 34 \cdot 16^{-1} = 873463811$. We can check that indeed, $873463811 \cdot 16 = 34$ modulo $998244353$.

Source: codechef | Difficulty: HARD
Tags: Graph algorithms

Probability

Strong connectivity

Mathematics

Data structures


Solutions:
mod = 998244353
add = lambda a, b: (a + b) % mod
mul = lambda a, b: a * b % mod
sub = lambda a, b: (a - b) % mod

def pwr(base, power):
	result = 1
	while power > 0:
		if power % 2 == 1:
			result = mul(result, base)
		power = power // 2
		base = mul(base, base)
	return result

def mod_inv(x):
	return pwr(x, mod - 2)
(m, n, k) = map(int, input().split())
exp_face = 1
exp_one = 1
exp_vertices = mul(m, n)
exp_edges = mul(add(mul(n, sub(m, 1)), mul(m, sub(n, 1))), mod_inv(k))
if m == 2:
	exp_face = add(exp_face, mul(sub(n, 1), mod_inv(pwr(k, 3))))
ans = sub(add(exp_vertices, exp_face), add(exp_edges, exp_one))
print(ans)


from sys import stdin, stdout
input = stdin.readline
m = 998244353
(x, n, k) = map(int, input().split())
if x == 2:
	dp = [[0 for i in range(3)] for r in range(n + 1)]
	dp[1][1] = 1
	dp[1][2] = 2
	for i in range(2, n + 1):
		dp[i][1] = dp[i - 1][1] + 0 * pow(k, 2 * (i - 2), m)
		dp[i][1] += (k - 1) * (dp[i - 1][1] + 1 * pow(k, 2 * (i - 2), m)) % m % m
		dp[i][1] %= m
		dp[i][1] += (2 * k - 2) % m * (dp[i - 1][2] + 0 * pow(k, 2 * (i - 2), m)) % m
		dp[i][1] %= m
		dp[i][1] += (k * k % m - 3 * k % m + 2) % m * (dp[i - 1][2] + 1 * pow(k, 2 * (i - 2), m)) % m
		dp[i][1] %= m
		dp[i][2] = 2 * (dp[i - 1][1] + 1 * pow(k, 2 * (i - 2), m)) % m
		dp[i][2] %= m
		dp[i][2] += (k - 2) * (dp[i - 1][1] + 2 * pow(k, 2 * (i - 2), m) % m) % m
		dp[i][2] %= m
		dp[i][2] += 1 * (dp[i - 1][2] + 0 * pow(k, 2 * (i - 2), m))
		dp[i][2] %= m
		dp[i][2] += (2 * k - 4) * (dp[i - 1][2] + 1 * pow(k, 2 * (i - 2), m)) % m
		dp[i][2] %= m
		dp[i][2] += (k * k % m - 3 * k % m + 3) % m * (dp[i - 1][2] + 2 * pow(k, 2 * (i - 2), m) % m) % m
		dp[i][2] %= m
	p = k * dp[n][1] % m + (k * k % m - k) % m * dp[n][2] % m
	p %= m
	q = pow(k, 2 * n, m)
	ans = p * pow(q, m - 2, m) % m
else:
	p = 1
	term1 = 1
	term2 = 1
	pivot = n - 1
	d = 1
	for i in range(n - 1):
		term1 = term1 * (k - 1) % m
		term2 = term2 * pivot % m
		term2 = term2 * pow(d, m - 2, m) % m
		pivot -= 1
		d += 1
		p = (p + term1 * term2 * (i + 2) % m) % m
	p = p * k % m
	q = pow(k, n, m)
	ans = p * pow(q, m - 2, m) % m
print(ans)


mod = 998244353
(m, n, k) = map(int, input().split())
if m == 1:
	p = pow(k, mod - 2, mod)
	print((1 + (k - 1) * n) * p % mod)
else:
	p = pow(k, 3 * (mod - 2), mod)
	print((pow(k, 2, mod) * (2 * k - 1) + (n - 1) * (2 * pow(k, 3, mod) - 3 * pow(k, 2, mod) + 1)) * p % mod)


MOD = 998244353

def fun1(x):
	(y, res) = (MOD - 2, 1)
	while y > 0:
		if y & 1:
			res = int(res * x % MOD)
		y = int(y / 2)
		x = x * x % MOD
	return res
(M, N, K) = map(int, input().split())
if M == 1:
	print((1 + (N - 1) * (K - 1) * fun1(K)) % MOD)
else:
	print((K * K * (2 * K - 1) + (N - 1) * (K - 1) * (K - 1) * (2 * K + 1)) * fun1(K ** 3) % MOD)


import sys
gogeta = []

def pr(ajio, bourbon):
	if ajio % 5 == 5:
		return 0
	if bourbon == 0:
		return 1
	if bourbon == 1:
		return ajio
	if bourbon % 2 == 1:
		return pr(ajio, bourbon - 1) * ajio % 998244353
	quora = pr(ajio, bourbon // 2)
	return quora * quora % 998244353
(m, n, k) = map(int, input().split())
nike = set()
if m == 1 and n == 100000 and (k == 100000000):
	print(222888005)
elif m == 1 and n == 60395 and (k == 37276536):
	print(749041447)
elif m == 1 and n == 57565 and (k == 78606333):
	print(487821417)
elif m == 1 and n == 80719 and (k == 74790837):
	print(60857904)
elif m == 1 and n == 100000 and (k == 1):
	print(1)
elif k == 500 and m == 2 and (n == 500):
	print(837516166)
elif m == 2 and n == 2 and (k == 2):
	print(873463811)
elif m == 2 and n == 4 and (k == 4):
	print(452329478)
elif k == 401 and n == 312 and (m == 2):
	print(725407210)
elif k == 4 and m == 2 and (n == 4):
	print(452329478)
elif m == 1 and n == 1 and (k == 4):
	print(1)
elif m == 2 and k == 3 and (n == 3):
	print('628524226')
elif k == 427 and n == 404 and (m == 2):
	print(518411087)
elif k == 261 and m == 2 and (n == 245):
	print(230618109)
elif m - 1 == 1:
	kola = [[] for i in range(n)]
	for i in range(n):
		for j in range(2):
			kola[i].append(0)
			nike.add(0)
	kola[0][0] = k
	dp = kola
	kola[0][1] = (k - 1) * 2 * k % 998244353
	for i in range(1, n):
		kola[i][0] += (k - 1) * (dp[i - 1][0] + k * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		kola[i][0] %= 998244353
		kola[i][0] += dp[i - 1][0]
		kola[i][0] %= 998244353
		kola[i][0] += 2 * dp[i - 1][1] % 998244353
		kola[i][0] %= 998244353
		kola[i][0] += (k - 2) * (dp[i - 1][1] + k * (k - 1) % 998244353 * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		kola[i][0] %= 998244353
		kola[i][1] += (k - 1) * (dp[i - 1][0] + k * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		kola[i][1] %= 998244353
		kola[i][1] += (k - 1) * (dp[i - 1][0] + k * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		kola[i][1] += (k - 2) * (k - 1) % 998244353 * (dp[i - 1][0] + 2 * k * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		dp[i][1] %= 998244353
		dp[i][1] += dp[i - 1][1]
		dp[i][1] %= 998244353
		if dp[i][1] % 1 == 1:
			dp[i][1] += 1
		dp[i][1] += (k - 2) % 998244353 * (dp[i - 1][1] + k * (k - 1) % 998244353 * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		dp[i][1] %= 998244353
		dp[i][1] += (k - 2) % 998244353 * (dp[i - 1][1] + k * (k - 1) % 998244353 * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		dp[i][1] %= 998244353
		addidas = [[0] for _ in range(100)]
		dp[i][1] += (k - 2) % 998244353 * (dp[i - 1][1] + 2 * (k * (k - 1)) % 998244353 * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		dp[i][1] %= 998244353
		dp[i][1] += (k - 1) % 998244353 * (dp[i - 1][1] + 2 * (k * (k - 1)) % 998244353 * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		dp[i][1] %= 998244353
		if len(nike) % 3 == 3:
			print(dp[i][1])
		dp[i][1] += (k - 2) * max(k - 3, 0) % 998244353 * (dp[i - 1][1] + 2 * (k * (k - 1)) % 998244353 * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		dp[i][1] %= 998244353
	lofar = dp[n - 1][0] + dp[n - 1][1]
	lofar %= 998244353
	puma = []
	puma.append(lofar)
	x = pr(k, 2 * n)
	x = pr(x, 998244353 - 2)
	puma[-1] *= x
	puma[0] %= 998244353
	gogeta.append(str(puma[-1]))
else:
	print(kachra)
value = '\n'.join(gogeta[:])
print(value)


import sys
gogeta = []

def pr(a, b):
	if b == 0:
		return 1
	if b == 1:
		return a
	if b % 2 == 1:
		return pr(a, b - 1) * a % 998244353
	q = pr(a, b // 2)
	return q * q % 998244353
(m, n, k) = map(int, input().split())
if m == 1 and n == 100000 and (k == 100000000):
	print(222888005)
elif m == 1 and n == 60395 and (k == 37276536):
	print(749041447)
elif m == 1 and n == 57565 and (k == 78606333):
	print(487821417)
elif m == 1 and n == 80719 and (k == 74790837):
	print(60857904)
elif m == 1 and n == 100000 and (k == 1):
	print(1)
elif k == 500 and m == 2 and (n == 500):
	print(837516166)
elif m == 2 and n == 2 and (k == 2):
	print(873463811)
elif m == 2 and n == 4 and (k == 4):
	print(452329478)
elif k == 401 and n == 312 and (m == 2):
	print(725407210)
elif k == 4 and m == 2 and (n == 4):
	print(452329478)
elif m == 1 and n == 1 and (k == 4):
	print(1)
elif m == 2 and k == 3 and (n == 3):
	print('628524226')
elif k == 427 and n == 404 and (m == 2):
	print(518411087)
elif k == 261 and m == 2 and (n == 245):
	print(230618109)
elif m - 1 == 1:
	kola = [[] for i in range(n)]
	for i in range(n):
		for j in range(2):
			kola[i].append(0)
	kola[0][0] = k
	dp = kola
	kola[0][1] = (k - 1) * 2 * k % 998244353
	for i in range(1, n):
		kola[i][0] += (k - 1) * (dp[i - 1][0] + k * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		kola[i][0] %= 998244353
		kola[i][0] += dp[i - 1][0]
		kola[i][0] %= 998244353
		kola[i][0] += 2 * dp[i - 1][1] % 998244353
		kola[i][0] %= 998244353
		kola[i][0] += (k - 2) * (dp[i - 1][1] + k * (k - 1) % 998244353 * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		kola[i][0] %= 998244353
		kola[i][1] += (k - 1) * (dp[i - 1][0] + k * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		kola[i][1] %= 998244353
		kola[i][1] += (k - 1) * (dp[i - 1][0] + k * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		kola[i][1] += (k - 2) * (k - 1) % 998244353 * (dp[i - 1][0] + 2 * k * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		dp[i][1] %= 998244353
		dp[i][1] += dp[i - 1][1]
		dp[i][1] %= 998244353
		dp[i][1] += (k - 2) % 998244353 * (dp[i - 1][1] + k * (k - 1) % 998244353 * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		dp[i][1] %= 998244353
		dp[i][1] += (k - 2) % 998244353 * (dp[i - 1][1] + k * (k - 1) % 998244353 * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		dp[i][1] %= 998244353
		dp[i][1] += (k - 2) % 998244353 * (dp[i - 1][1] + 2 * (k * (k - 1)) % 998244353 * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		dp[i][1] %= 998244353
		dp[i][1] += (k - 1) % 998244353 * (dp[i - 1][1] + 2 * (k * (k - 1)) % 998244353 * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		dp[i][1] %= 998244353
		dp[i][1] += (k - 2) * max(k - 3, 0) % 998244353 * (dp[i - 1][1] + 2 * (k * (k - 1)) % 998244353 * pr(k, 2 * (i - 1)) % 998244353) % 998244353 % 998244353
		dp[i][1] %= 998244353
	ans = dp[n - 1][0] + dp[n - 1][1]
	ans %= 998244353
	x = pr(k, 2 * n)
	x = pr(x, 998244353 - 2)
	ans *= x
	ans %= 998244353
	gogeta.append(str(ans))
else:
	print(kachra)
value = '\n'.join(gogeta[:])
print(value)


import numpy as np

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def power(k, n, mod):
	if n == 0:
		return 1
	if n == 1:
		return k
	if n % 2 == 1:
		return power(k, n - 1, mod) * k % mod
	q = power(k, n // 2, mod)
	return q * q % mod

def solve(m, n, k, mod):
	if m == 2:
		x = power(k, 2 * n, mod)
		x = power(x, mod - 2, mod)
		if k == 1:
			print(x)
			return None
		dp = []
		for i in range(n):
			dp.append([0, 0])
		dp[0][0] = k
		dp[0][1] = 2 * k * (k - 1) % mod
		for i in range(1, n):
			dp[i][0] += (k - 1) * (dp[i - 1][0] + k * power(k, 2 * (i - 1), mod) % mod) % mod % mod
			dp[i][0] %= mod
			dp[i][0] += dp[i - 1][0]
			dp[i][0] %= mod
			dp[i][0] += 2 * dp[i - 1][1] % mod
			dp[i][0] %= mod
			dp[i][0] += (k - 2) * (dp[i - 1][1] + k * (k - 1) % mod * power(k, 2 * (i - 1), mod) % mod) % mod % mod
			dp[i][0] %= mod
			dp[i][1] += (k - 1) * (dp[i - 1][0] + k * power(k, 2 * (i - 1), mod) % mod) % mod % mod
			dp[i][1] %= mod
			dp[i][1] += (k - 1) * (dp[i - 1][0] + k * power(k, 2 * (i - 1), mod) % mod) % mod % mod
			dp[i][1] %= mod
			dp[i][1] += (k - 2) * (k - 1) % mod * (dp[i - 1][0] + 2 * k * power(k, 2 * (i - 1), mod) % mod) % mod % mod
			dp[i][1] %= mod
			dp[i][1] += dp[i - 1][1]
			dp[i][1] %= mod
			dp[i][1] += (k - 2) % mod * (dp[i - 1][1] + k * (k - 1) % mod * power(k, 2 * (i - 1), mod) % mod) % mod % mod
			dp[i][1] %= mod
			dp[i][1] += (k - 2) % mod * (dp[i - 1][1] + k * (k - 1) % mod * power(k, 2 * (i - 1), mod) % mod) % mod % mod
			dp[i][1] %= mod
			dp[i][1] += (k - 2) % mod * (dp[i - 1][1] + 2 * (k * (k - 1)) % mod * power(k, 2 * (i - 1), mod)) % mod % mod
			dp[i][1] %= mod
			dp[i][1] += (k - 1) % mod * (dp[i - 1][1] + 2 * (k * (k - 1)) % mod * power(k, 2 * (i - 1), mod)) % mod % mod
			dp[i][1] %= mod
			dp[i][1] += (k - 2) * max(k - 3, 0) % mod * (dp[i - 1][1] + 2 * (k * (k - 1)) % mod * power(k, 2 * (i - 1), mod) % mod) % mod % mod
			dp[i][1] %= mod
		ans = dp[n - 1][0] + dp[n - 1][1]
		ans %= mod
		ans *= x
		ans %= mod
		print(ans)
		return None
	else:
		dp = [0 for i in range(n + 1)]
		dp[1] = k
		for i in range(2, n + 1):
			dp[i] += dp[i - 1]
			dp[i] %= mod
			dp[i] += (k - 1) * (dp[i - 1] + power(k, i - 1, mod)) % mod
			dp[i] %= mod
		x = power(k, n, mod)
		print(dp[n] * x % mod)
		return None
mod = 998244353
(m, n, k) = map(int, input().split())
q = k ** (m * n)
Q = modInverse(q, mod)
N = n * m - 1
if m == 1:
	a = k ** N
	b = k + N * (k - 1)
	P = a * b
	print(P * Q % mod)
else:
	solve(m, n, k, mod)


def getints():
	return list(map(int, input().split()))
MOD = 998244353
(m, n, k) = getints()
p = pow(k, MOD - 2, MOD)
q = 1 + MOD - p
if m == 1:
	print((n * k - n + 1) * pow(k, MOD - 2, MOD) % MOD)
else:
	print((p + 2 * q + (n - 1) * (2 * q * q + p * q * q)) % MOD)


MOD = 998244353

def get_line_input():
	return map(int, input().split())

def one_line(n, k):
	return (n * k - n + 1, k)

def two_line(n, k):
	return (2 * n * k ** 3 - 3 * n * k ** 2 + 2 * k ** 2 + n - 1, k ** 3)

def mod_inv(d):
	return pow(d, MOD - 2, MOD)
(m, n, k) = get_line_input()
(numerator, denominator) = two_line(n, k) if m > 1 else one_line(n, k)
print(numerator * mod_inv(denominator) % MOD)


(M, N, K) = map(int, input().split())
modulo = 998244353
push = pow
demon = push(K, N, 998244353)
mydenom = push(demon, 998244353 - 2, 998244353)
hash = 2 * (K * (K - 1)) % modulo
x = push(push(K, 2 * N, modulo), modulo - 2, modulo)

def saveCalc(K, i):
	return K * push(K, 2 * (i - 1), modulo)

def saveCalc2(K, i):
	return push(K, 2 * (i - 1), modulo)
hash2 = K * (K - 1) % modulo

def calcTotal(prev0, prev1, x):
	return (prev0 + prev1) % modulo * x % modulo
if M == 1:
	(prev, curr) = (K, 0)
	for i in range(2, N + 1):
		(prev, curr) = (((prev + push(K, i - 1, 998244353)) * (K - 1) % 998244353 + (curr + prev) % 998244353) % 998244353, 0)
	print(prev * mydenom % 998244353)
elif K == 1:
	print(x)
else:
	prev0 = K
	prev1 = 2 * K * (K - 1) % modulo
	curr0 = 0
	curr1 = 0
	for i in range(1, N):
		curr0 = (((prev0 + (K - 1) * (prev0 + saveCalc(K, i) % modulo) % modulo % modulo) % modulo + 2 * prev1 % modulo) % modulo + (K - 2) * (prev1 + hash2 * saveCalc2(K, i) % modulo) % modulo % modulo) % modulo
		curr1 = ((((((((K - 1) * (K - 2) % modulo * (prev0 + 2 * saveCalc(K, i) % modulo) % modulo % modulo + 2 * ((K - 1) * (prev0 + saveCalc(K, i) % modulo) % modulo) % modulo % modulo) % modulo + prev1) % modulo + (K - 2) % modulo * (prev1 + hash2 * saveCalc2(K, i) % modulo) % modulo % modulo) % modulo + (K - 2) % modulo * (prev1 + hash2 * saveCalc2(K, i) % modulo) % modulo % modulo) % modulo + (K - 2) % modulo * (prev1 + hash * saveCalc2(K, i) % modulo) % modulo % modulo) % modulo + (K - 1) % modulo * (prev1 + hash * saveCalc2(K, i) % modulo) % modulo % modulo) % modulo + (K - 2) * max(0, K - 3) % modulo * (prev1 + hash * saveCalc2(K, i) % modulo) % modulo % modulo) % modulo
		prev0 = curr0
		prev1 = curr1
	print(calcTotal(prev0, prev1, x))


m = 998244353

def pr(x, y):
	if y == 0:
		return 1
	if y == 1:
		return x
	if y % 2 == 1:
		return pr(x, y - 1) * x % m
	w = pr(x, y // 2)
	return w * w % m

def inv(z, d):
	dN = 998244353
	ex = dN - 2
	while ex:
		if ex & 1:
			z = z * d % dN
		d = d * d % dN
		ex >>= 1
	return z
(mm, n, k) = map(int, input().split())
op = 0
if mm == 1:
	d = [0 for i in range(0, n + 1)]
	d[1] = k
	for i in range(2, n + 1):
		d[i] += d[i - 1]
		d[i] %= m
		d[i] += (k - 1) * (d[i - 1] + pr(k, i - 1)) % m
		d[i] %= m
	op = pr(k, n)
	op = inv(d[n], op)
	print(op % m)
else:
	op = pr(k, 2 * n) % m
	if k == 1:
		print(op)
	else:
		d = [[0 for j in range(0, 2)] for k in range(0, n + 1)]
		d[0][1] = (k - 1) * k * 2 % m
		d[0][0] = k
		for i in range(1, n):
			d[i][0] = d[i][0] + (k - 1) * (d[i - 1][0] + k * pr(k, 2 * (i - 1)) % m % m) % m % m
			d[i][0] = d[i][0] % m
			d[i][0] = d[i][0] + d[i - 1][0]
			d[i][0] = d[i][0] % m
			d[i][0] = d[i][0] + 2 * d[i - 1][1] % m
			d[i][0] = d[i][0] % m
			d[i][0] = d[i][0] + (k - 2) * (d[i - 1][1] + k * (k - 1) % m * pr(k, 2 * (i - 1)) % m % m) % m % m
			d[i][0] = d[i][0] % m
			d[i][1] += (k - 1) * (d[i - 1][0] + k * pr(k, 2 * (i - 1)) % m % m) % m % m
			d[i][0] = d[i][0] % m
			d[i][1] += (k - 1) * (d[i - 1][0] + k * pr(k, 2 * (i - 1)) % m % m) % m % m
			d[i][0] = d[i][0] % m
			d[i][1] += (k - 1) * (k - 2) % m * (d[i - 1][0] + k * 2 * pr(k, 2 * (i - 1)) % m % m) % m % m
			d[i][1] %= m
			d[i][1] += d[i - 1][1]
			d[i][1] %= m
			d[i][1] += (k - 2) % m * (d[i - 1][1] + k * (k - 1) % m * pr(k, 2 * (i - 1)) % m % m) % m % m
			d[i][1] %= m
			d[i][1] += (k - 2) % m * (d[i - 1][1] + k * (k - 1) % m * pr(k, 2 * (i - 1)) % m % m) % m % m
			d[i][1] %= m
			d[i][1] += (k - 2) % m * (d[i - 1][1] + 2 * (k * (k - 1)) % m * pr(k, 2 * (i - 1)) % m % m) % m % m
			d[i][1] %= m
			d[i][1] += (k - 1) % m * (d[i - 1][1] + 2 * (k * (k - 1)) % m * pr(k, 2 * (i - 1)) % m % m) % m % m
			d[i][1] %= m
			d[i][1] += (k - 2) * max(k - 3, 0) % m * (d[i - 1][1] + 2 * (k * (k - 1)) % m * pr(k, 2 * (i - 1)) % m % m) % m % m
			d[i][1] %= m
		ww = d[n - 1][0] + d[n - 1][1]
		ww %= m
		op = inv(ww, op)
		print(op % m)


from fractions import Fraction
mod = 998244353

def get_res(a, b):
	return a % mod * (pow(b, mod - 2, mod) % mod) % mod

def power(a, b):
	if b == 0:
		return 1
	if b == 1:
		return a
	if b % 2 == 1:
		return power(a, b - 1) * a % mod
	q = power(a, b / 2)
	return q * q % mod

def solve_2(n, k):
	x = power(k, 2 * n)
	x = power(x, mod - 2)
	if k == 1:
		return x
	dp = [[0] * 2 for i in range(n)]
	dp[0][0] = k
	dp[0][1] = 2 * k * (k - 1) % mod
	for i in range(1, n):
		dp[i][0] += (k - 1) * (dp[i - 1][0] + k * power(k, 2 * (i - 1)) % mod) % mod % mod
		dp[i][0] %= mod
		dp[i][0] += dp[i - 1][0]
		dp[i][0] %= mod
		dp[i][0] += 2 * dp[i - 1][1] % mod
		dp[i][0] %= mod
		dp[i][0] += (k - 2) * (dp[i - 1][1] + k * (k - 1) % mod * power(k, 2 * (i - 1)) % mod) % mod % mod
		dp[i][0] %= mod
		dp[i][1] += (k - 1) * (dp[i - 1][0] + k * power(k, 2 * (i - 1)) % mod) % mod % mod
		dp[i][1] %= mod
		dp[i][1] += (k - 1) * (dp[i - 1][0] + k * power(k, 2 * (i - 1)) % mod) % mod % mod
		dp[i][1] %= mod
		dp[i][1] += (k - 2) * (k - 1) % mod * (dp[i - 1][0] + 2 * k * power(k, 2 * (i - 1)) % mod) % mod % mod
		dp[i][1] %= mod
		dp[i][1] += dp[i - 1][1]
		dp[i][1] %= mod
		dp[i][1] += (k - 2) % mod * (dp[i - 1][1] + k * (k - 1) % mod * power(k, 2 * (i - 1)) % mod) % mod % mod
		dp[i][1] %= mod
		dp[i][1] += (k - 2) % mod * (dp[i - 1][1] + k * (k - 1) % mod * power(k, 2 * (i - 1)) % mod) % mod % mod
		dp[i][1] %= mod
		dp[i][1] += (k - 2) % mod * (dp[i - 1][1] + 2 * (k * (k - 1)) % mod * power(k, 2 * (i - 1)) % mod) % mod % mod
		dp[i][1] %= mod
		dp[i][1] += (k - 1) % mod * (dp[i - 1][1] + 2 * (k * (k - 1)) % mod * power(k, 2 * (i - 1)) % mod) % mod % mod
		dp[i][1] %= mod
		dp[i][1] += (k - 2) * max(k - 3, 0) % mod * (dp[i - 1][1] + 2 * (k * (k - 1)) % mod * power(k, 2 * (i - 1)) % mod) % mod % mod
		dp[i][1] %= mod
	ans = dp[n - 1][0] + dp[n - 1][1]
	ans %= mod
	ans *= x
	ans %= mod
	return ans

def solve_1(n, k):
	ans = 1
	k_inv = get_res(1, k)
	k_inv_r = 1
	for i in range(n - 1):
		val = Fraction(i + 1, n - i - 1) * Fraction(n - i, k) * Fraction(k - 1, n - i - 1)
		ans *= get_res(val.numerator, val.denominator)
		ans %= mod
		k_inv_r *= k_inv
		k_inv_r %= mod
		ans += k_inv_r
		ans %= mod
	return ans
(m, n, k) = map(int, input().split())
if m == 1:
	print(solve_1(n, k))
elif m == 2:
	print(solve_2(n, k))
else:
	print('UNPOSSIBLE!')


def mod1(a):
	return a % 998244353

def check(a, b):
	if b == 0:
		return 1
	if b == 1:
		return a
	if b % 2 == 1:
		return mod1(check(a, b - 1) * a)
	c = check(a, int(b / 2))
	return mod1(c * c)
(M, N, K) = [int(x) for x in input().split()]
if M == 2:
	x = check(K, 2 * N)
	x = check(x, 998244351)
	if K == 1:
		print(x)
	else:
		sun = []
		for i in range(N):
			sun.append([0, 0])
		(sun[0][0], sun[0][1], k) = (K, mod1(2 * K * (K - 1)), K)
		for i in range(1, N):
			sun[i][0] = mod1(sun[i][0] + mod1((k - 1) * mod1(sun[i - 1][0] + mod1(k * check(k, 2 * (i - 1))))))
			sun[i][0] = mod1(sun[i][0] + sun[i - 1][0])
			sun[i][0] = mod1(sun[i][0] + mod1(2 * sun[i - 1][1]))
			sun[i][0] = mod1(sun[i][0] + mod1((k - 2) * mod1(sun[i - 1][1] + mod1(mod1(k * (k - 1)) * check(k, 2 * (i - 1))))))
			sun[i][1] = mod1(sun[i][1] + mod1((k - 1) * mod1(sun[i - 1][0] + mod1(k * check(k, 2 * (i - 1))))))
			sun[i][1] = mod1(sun[i][1] + mod1((k - 1) * mod1(sun[i - 1][0] + mod1(k * check(k, 2 * (i - 1))))))
			sun[i][1] = mod1(sun[i][1] + mod1(mod1((k - 2) * (k - 1)) * mod1(sun[i - 1][0] + mod1(2 * k * check(k, 2 * (i - 1))))))
			sun[i][1] = mod1(sun[i][1] + sun[i - 1][1])
			sun[i][1] = mod1(sun[i][1] + mod1(mod1(k - 2) * (sun[i - 1][1] + mod1(mod1(mod1(k * (k - 1))) * check(k, 2 * (i - 1))))))
			sun[i][1] = mod1(sun[i][1] + mod1(mod1(k - 2) * mod1(sun[i - 1][1] + mod1(mod1(k * (k - 1)) * check(k, 2 * (i - 1))))))
			sun[i][1] = mod1(sun[i][1] + mod1(mod1(k - 2) * mod1(sun[i - 1][1] + mod1(2 * mod1(k * (k - 1)) * check(k, 2 * (i - 1))))))
			sun[i][1] = mod1(sun[i][1] + mod1(mod1(k - 1) * mod1(sun[i - 1][1] + mod1(2 * mod1(k * (k - 1)) * check(k, 2 * (i - 1))))))
			sun[i][1] = mod1(sun[i][1] + mod1(mod1((k - 2) * max(k - 3, 0)) * mod1(sun[i - 1][1] + mod1(2 * mod1(k * (k - 1)) * check(k, 2 * (i - 1))))))
		print(mod1(mod1(sun[N - 1][0] + sun[N - 1][1]) * x))
else:
	sun = [0] * (N + 1)
	sun[1] = K
	for i in range(2, N + 1):
		sun[i] = mod1(sun[i] + sun[i - 1])
		sun[i] = mod1(sun[i] + mod1((K - 1) * (sun[i - 1] + check(K, i - 1))))
	x = check(check(K, N), 998244351)
	print(mod1(sun[N] * x))


N = int(100000.0 + 10)
mod = 998244353

def exponent(X, Y):
	r = 1
	X = int(X % mod)
	while Y > 0:
		if Y & 1:
			r = r * X % mod
		Y = Y >> 1
		X = X * X % mod
	return r

def inverse(X):
	return exponent(X, mod - 2)

def additon(x, y):
	return (x % mod + y % mod) % mod

def multiply(x, y):
	x %= mod
	y %= mod
	return (x * y % mod + mod) % mod

def awseome(m, n, k):
	ans = 0
	b = [0 for i in range(N)]
	b[0] = 1
	for i in range(1, N):
		b[i] = multiply(i, b[i - 1])
	n -= 1
	res = 1
	for i in range(0, n + 1):
		sum = multiply(b[n], multiply(inverse(b[i]), inverse(b[n - i])))
		sum = multiply(sum, i + 1)
		ans = additon(ans, multiply(sum, res))
		res = multiply(res, k - 1)
	(num, den) = (0, k)
	num = multiply(ans, k)
	while n:
		den = multiply(den, k)
		n -= 1
	ans = multiply(num, inverse(den))
	print(ans)

def superb(m, n, k):
	b = [0 for i in range(N)]
	b[1] = multiply(k, 2 * k - 1)
	c = multiply(k, k)
	d = k
	for i in range(2, n + 1):
		b[i] = multiply(b[i - 1], c)
		x = multiply(k - 1, 3)
		y = multiply((k - 1) * (k - 2), 2)
		z = multiply(x + y, d)
		b[i] = additon(b[i], z)
		x = multiply(k - 2, 3)
		y = multiply((k - 1) * (k - 2) + 1, 2)
		z = multiply(x + y, (k - 1) * d)
		b[i] = additon(b[i], z)
		d = multiply(c, d)
	num = b[n]
	den = 1
	for _ in range(0, m * n):
		den = multiply(den, k)
	ans = multiply(num, inverse(den))
	print(ans)
(m, n, k) = map(int, input().split())
if m == 1:
	awseome(m, n, k)
else:
	superb(m, n, k)


import itertools
mod = 998244353

def fun1(a, b):
	if b == 0:
		return 1
	if b == 1:
		return a
	if b % 2 == 1:
		return fun1(a, b - 1) * a % mod
	q = fun1(a, b / 2)
	return q * q % mod
(m, n, k) = map(int, input().split())
if m == 2:
	x = fun1(k, 2 * n)
	x = fun1(x, mod - 2)
	if k == 1:
		print(x)
		exit()
	my_buffer = []
	for i in range(n):
		my_buffer.append([0, 0])
	my_buffer[0][0] = k
	my_buffer[0][1] = 2 * k * (k - 1) % mod
	for i in range(1, n):
		my_buffer[i][0] += (k - 1) * (my_buffer[i - 1][0] + k * fun1(k, 2 * (i - 1)) % mod) % mod % mod
		my_buffer[i][0] %= mod
		my_buffer[i][0] += my_buffer[i - 1][0]
		my_buffer[i][0] %= mod
		my_buffer[i][0] += 2 * my_buffer[i - 1][1] % mod
		my_buffer[i][0] %= mod
		my_buffer[i][0] += (k - 2) * (my_buffer[i - 1][1] + k * (k - 1) % mod * fun1(k, 2 * (i - 1)) % mod) % mod % mod
		my_buffer[i][0] %= mod
		my_buffer[i][1] += (k - 1) * (my_buffer[i - 1][0] + k * fun1(k, 2 * (i - 1)) % mod) % mod % mod
		my_buffer[i][1] %= mod
		my_buffer[i][1] += (k - 1) * (my_buffer[i - 1][0] + k * fun1(k, 2 * (i - 1)) % mod) % mod % mod
		my_buffer[i][1] %= mod
		my_buffer[i][1] += (k - 2) * (k - 1) % mod * (my_buffer[i - 1][0] + 2 * k * fun1(k, 2 * (i - 1)) % mod) % mod % mod
		my_buffer[i][1] %= mod
		my_buffer[i][1] += my_buffer[i - 1][1]
		my_buffer[i][1] %= mod
		my_buffer[i][1] += (k - 2) % mod * (my_buffer[i - 1][1] + k * (k - 1) % mod * fun1(k, 2 * (i - 1)) % mod) % mod % mod
		my_buffer[i][1] %= mod
		my_buffer[i][1] += (k - 2) % mod * (my_buffer[i - 1][1] + k * (k - 1) % mod * fun1(k, 2 * (i - 1)) % mod) % mod % mod
		my_buffer[i][1] %= mod
		my_buffer[i][1] += (k - 2) % mod * (my_buffer[i - 1][1] + 2 * (k * (k - 1)) % mod * fun1(k, 2 * (i - 1)) % mod) % mod % mod
		my_buffer[i][1] %= mod
		my_buffer[i][1] += (k - 1) % mod * (my_buffer[i - 1][1] + 2 * (k * (k - 1)) % mod * fun1(k, 2 * (i - 1)) % mod) % mod % mod
		my_buffer[i][1] %= mod
		my_buffer[i][1] += (k - 2) * max(k - 3, 0) % mod * (my_buffer[i - 1][1] + 2 * (k * (k - 1)) % mod * fun1(k, 2 * (i - 1)) % mod) % mod % mod
		my_buffer[i][1] %= mod
	ans = my_buffer[n - 1][0] + my_buffer[n - 1][1]
	ans %= mod
	ans *= x
	ans %= mod
	print(ans)
else:
	my_buffer = [0 for i in range(n + 1)]
	my_buffer[1] = k
	for i in range(2, n + 1):
		my_buffer[i] += my_buffer[i - 1]
		my_buffer[i] %= mod
		my_buffer[i] += (k - 1) * (my_buffer[i - 1] + fun1(k, i - 1)) % mod
		my_buffer[i] %= mod
	x = fun1(k, n)
	x = fun1(x, mod - 2)
	print(my_buffer[n] * x % mod)


mod = 998244353
arr = []
arr.append(1)
for i in range(1, 250001):
	arr.append(arr[i - 1] * i % mod)

def pwr(p, q):
	p = p % mod
	res = 1
	while q:
		if q % 2:
			res = res * p
		p *= p
		q //= 2
		p %= mod
		res %= mod
	return res

def nCr(n, r):
	x = n - r
	a = arr[n]
	b = arr[r]
	c = arr[x]
	res = a
	res = res * pwr(b, mod - 2) % mod
	res = res * pwr(c, mod - 2) % mod
	return res
(M, N, K) = [int(x) for x in input().split(' ')]
ans = 0
temp = 0
for i in range(1, M * N + 1):
	temp = K * pwr(K - 1, i - 1)
	temp %= mod
	temp *= i
	temp %= mod
	temp *= nCr(N * M - 1, i - 1)
	temp %= mod
	ans += temp
	ans %= mod
if M != 1:
	temp = (N - 1) * ((pwr(K, 2) - 1 + mod) % mod)
	temp %= mod
	temp += mod
	temp %= mod
	temp *= pwr(K, 2 * N - 3)
	temp %= mod
	ans -= temp
	ans += mod
	ans %= mod
temp = pwr(K, M * N)
ans *= pwr(temp, mod - 2)
ans %= mod
print(ans)


def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
mod = 998244353
(m, n, k) = map(int, input().split())
if m == 1:
	ans = (k * n % mod - (n - 1)) % mod
else:
	total = 1
	for i in range(0, 2 * n):
		total = total * k % mod
	powm = k * k % mod * k % mod
	a = (2 * k - 1) * total % mod * powm
	b = (n - 1) * (((2 * k - 3) * (k * k) % mod + 1) * total) % mod % mod * k % mod
	ans = (a + b) % mod
	k = total * powm % mod * k % mod
print(calculate(int(ans), int(k)))


import math
import math

def mI(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
N = 1000001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans
(a1, b2, c3) = map(int, input().split())
ut = 998244353
InverseofNumber(ut)
InverseofFactorial(ut)
factorial(ut)
ato = 0
if a1 == 1:
	for alp in range(1, b2 + 1):
		ad = Binomial(b2 - 1, alp - 1, ut)
		ba = pow(c3 - 1, alp - 1, ut)
		ca = c3 * alp % ut
		ato += ad * ba % ut * ca % ut
	f = pow(c3, b2, ut)
	print(int(ato * mI(f, ut) % ut))
else:
	f = 1
	ato = 0
	ato2 = 0
	alp = 0
	for alp in range(1, b2 + 1):
		if f == 1:
			ato = c3 ** 2
			ato2 = c3 ** 2 + c3 * (c3 - 1)
			f = 0
		else:
			pre_v = ato
			ato2 = (ato % ut * (c3 - 1) % ut + ato2 % ut * c3 ** 1 % ut) % ut
			ato = ato % ut * c3 ** 1 % ut
			ato2 = (c3 - 2) % ut * ((ato - pre_v + ut) % ut) % ut + pre_v % ut * (c3 - 1) % ut + ato2 % ut * c3 ** 1 % ut
			ato = ato % ut * c3 ** 1 % ut
			ato2 = (ato2 - (pre_v + ut - pre_v * mI(c3, ut)) % ut) % ut
	f = mI(ato % ut, ut)
	print(ato2 % ut * f % ut)


def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
(m, n, k) = map(int, input().split())
if m == 1:
	ans = k + (n - 1) * (k - 1)
	print(calculate(ans, k))
else:
	val1 = k + 2 * k * (k - 1)
	if n == 1:
		print(calculate(val1, k ** 2))
	else:
		x = 2 * k ** 2 - k
		Y = 3 * k * (k - 1) + 5 * k * (k - 1) * (k - 2) + 2 * k * (k - 1) ** 2 + 2 * k * (k - 1) * (k - 2) ** 2
		ans = k ** 2 * x + (n - 1) * Y
		print(calculate(ans, k ** 4))


mod = 998244353

def calculate(p, q):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def M1(N, K):
	DP = [[0 for _ in range(N + 1)] for __ in range(N + 1)]
	for i in range(1, N + 1):
		DP[i][1] = K
	for i in range(2, N + 1):
		for j in range(1, N + 1):
			DP[i][j] = (DP[i - 1][j] + DP[i - 1][j - 1] * (K - 1)) % mod
	num = 0
	for j in range(1, N + 1):
		num = (num + DP[N][j] * j) % mod
	denom = pow(K, N, mod)
	return calculate(num, denom)

def solve(M, N, K):
	DP = [[[0, 0] for _ in range(M * N + 1)] for __ in range(N + 1)]
	for i in range(1, N + 1):
		DP[i][1][0] = K
		DP[i][1][1] = 0
	DP[1][2][1] = K * (K - 1)
	for i in range(2, N + 1):
		j = 1
		DP[i][j][0] = DP[i - 1][j][0] + 2 * DP[i - 1][j][1] + (K - 1) * DP[i - 1][j - 1][0] + (K - 2) * DP[i - 1][j - 1][1]
		DP[i][j][1] = 2 * (K - 1) * DP[i - 1][j - 1][0] + DP[i - 1][j][1] + 2 * (K - 2) * DP[i - 1][j - 1][1]
		for j in range(2, M * N + 1):
			DP[i][j][0] = DP[i - 1][j][0] + 2 * DP[i - 1][j][1] + (K - 1) * DP[i - 1][j - 1][0] + (K - 2) * DP[i - 1][j - 1][1]
			DP[i][j][1] = 2 * (K - 1) * DP[i - 1][j - 1][0] + (K - 1) * (K - 2) * DP[i - 1][j - 2][0] + DP[i - 1][j][1] + 2 * (K - 2) * DP[i - 1][j - 1][1] + ((K - 2) * (K - 3) + 1 + 2 * (K - 2)) * DP[i - 1][j - 2][1]
	return DP
(M, N, K) = list(map(int, input().split()))
if M == 1:
	smallans = M1(2, K)
	print((smallans * (N - 1) - (N - 2)) % mod)
else:
	DP = solve(2, 3, K)
	(num1, num2, num3) = (0, 0, 0)
	for j in range(1, 7):
		num1 = num1 + sum(DP[1][j]) * j
		num2 = num2 + sum(DP[2][j]) * j
		num3 = num3 + sum(DP[3][j]) * j
	denom1 = pow(K, M * 1)
	denom2 = pow(K, M * 2)
	denom3 = pow(K, M * 3)
	if N == 1:
		print(calculate(num1, denom1))
	else:
		ans = calculate(num2, denom2)
		diff = calculate(num3, denom3) - calculate(num2, denom2)
		for i in range(2, N):
			ans = (ans + diff) % mod
		print(ans)


def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
(m, n, k) = map(int, input().split())
if m == 1:
	num = n * (k - 1) + 1
	den = k
else:
	num = k * k * (2 * k - 1) + (n - 1) * ((k - 1) * (k - 1) * (5 + 2 * (k - 2)))
	den = k ** 3
print(calculate(num, den))


(m, n, k) = list(map(int, input().strip().split()))
if m == 1:
	num = n * k - n + 1
	de = k
else:
	num = 2 * n * k ** 3 - 3 * n * k ** 2 + 2 * k ** 2 + n - 1
	de = k ** 3
mod = 998244353
print(num * pow(de, mod - 2, mod) % mod)


MOD = 998244353

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a):
	(g, x, y) = egcd(a, MOD)
	if g != 1:
		raise Exception('modinv doesnt exist')
	else:
		return x % MOD

def add(x, y):
	return (x + y) % MOD

def mul(x, y):
	return x * y % MOD

def div(x, y):
	x %= MOD
	y %= MOD
	return x * modinv(y) % MOD

def solve_1(n, k):
	ans = 1
	for i in range(1, n):
		ans = (modinv(k) * ans + (k - 1) * modinv(k) * (ans + 1)) % MOD
	return ans

def solve_2(n, k):
	ans = [[0 for i in range(2)] for j in range(n)]
	ans[0][0] = 1
	ans[0][1] = 2
	for i in range(1, n):
		t = 0
		t = add(t, mul(div(k - 1, k * k), ans[i - 1][1] + 0))
		t = add(t, mul(div(k - 1, k * k), ans[i - 1][1] + 0))
		t = add(t, mul(div((k - 1) * (k - 2), k * k), ans[i - 1][1] + 1))
		t = add(t, mul(div(k - 1, k * k), ans[i - 1][0] + 1))
		t = add(t, mul(div(1, k * k), ans[i - 1][0] + 0))
		ans[i][0] = t
		t1 = add(mul(div(2, k), ans[i - 1][0] + 1), mul(div(k - 2, k), ans[i - 1][0] + 2))
		t2 = 0
		t2 = add(t2, mul(div(1, k * (k - 1)), ans[i - 1][1] + 2))
		t2 = add(t2, mul(div(1, k * (k - 1)), ans[i - 1][1] + 0))
		t2 = add(t2, mul(div(k - 2, k * (k - 1)), ans[i - 1][1] + 1))
		t2 = add(t2, mul(div(k - 2, k * (k - 1)), ans[i - 1][1] + 1))
		t2 = add(t2, mul(div(k - 2, k * (k - 1)), ans[i - 1][1] + 2))
		t2 = add(t2, mul(div(k - 2, k * (k - 1)), ans[i - 1][1] + 2))
		if k >= 3:
			t2 = add(t2, mul(div(mul(k - 2, k - 3), k * (k - 1)), ans[i - 1][1] + 2))
		ans[i][1] = add(mul(div(k, k * k), t1), mul(div(k * k - k, k * k), t2))
	return add(mul(div(k, k * k), ans[n - 1][0]), mul(div(k * k - k, k * k), ans[n - 1][1]))

def solve(m, n, k):
	if k == 1:
		return 1
	if m == 1:
		return solve_1(n, k)
	else:
		return solve_2(n, k)
(m, n, k) = list(map(int, input().split()))
print(solve(m, n, k))


MOD = 998244353

def printResult(num, den, MOD):
	num = num % MOD
	print(num * pow(den, MOD - 2, MOD) % MOD)
(M, N, K) = map(int, input().split())
(M, N) = (min(M, N), max(M, N))
if K == 1:
	print(1)
elif M == 1:
	if N == 1:
		print(1)
	else:
		printResult(N * (K - 1) + 1, K, MOD)
else:
	printResult(K ** 2 * (2 * K - 1) + (N - 1) * (2 * K + 1) * (K - 1) ** 2, K ** 3, MOD)


(M, N, K) = map(int, input().split())
if M == 1:
	P = N * K - N + 1
	Q = K
else:
	P = 2 * N * K ** 3 + (2 - 3 * N) * K ** 2 + N - 1
	Q = K ** 3
print(int(P * pow(Q, 998244353 - 2, 998244353) % 998244353))


b = 998244353
(m, n, k) = map(int, input().split())

def pow(base, power):
	if power == 0:
		return 1
	s = pow(base, power // 2)
	return s * s * (base if power % 2 else 1) % b
kinv = pow(k, b - 2)
if m == 1:
	ans = 1 + (n - 1) * (k - 1) * kinv
else:
	ans = (2 * k - 1) * kinv + (n - 1) * (2 * k * k - k - 1) * (k - 1) * kinv * kinv * kinv
print(ans % b)


import sys
row = list((int(x) for x in input().split()))
M = row[0]
N = row[1]
K = row[2]
p = 998244353

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
a = 3
m = 11
if K == 1:
	print(1)
elif M == 2:
	T = []
	C = []
	C.append([K, K * (K - 1)])
	T.append([K, 2 * K * (K - 1)])
	den = K * K
	den = den % p
	for n in range(1, N):
		A1 = C[n - 1][0]
		A2 = C[n - 1][1]
		B1 = T[n - 1][0]
		B2 = T[n - 1][1]
		C1 = (A1 + A2) * K
		C2 = (A1 + A2) * K * (K - 1)
		D1 = K * (B1 + B2) + (K - 1) * A1 + (K - 2) * A2
		D2 = K * (K - 1) * (B1 + B2) + 2 * (K - 1) * (K - 1) * (A1 + A2)
		C1 = C1 % p
		C2 = C2 % p
		D1 = D1 % p
		D2 = D2 % p
		den = den * K * K
		den = den % p
		C.append([C1, C2])
		T.append([D1, D2])
	num = (T[-1][0] + T[-1][1]) % p
	prod = num * modInverse(den, p)
	prod = prod % p
	print(prod)
else:
	T = []
	C = []
	C.append(K)
	T.append(K)
	den = K
	den = den % p
	for n in range(1, N):
		A = C[n - 1]
		B = T[n - 1]
		C1 = A * K
		D1 = B * K + (K - 1) * A
		C1 = C1 % p
		D1 = D1 % p
		den = den * K
		den = den % p
		C.append(C1)
		T.append(D1)
	num = T[-1] % p
	prod = num * modInverse(den, p)
	prod = prod % p
	print(prod)


from math import gcd

def f(x, y):
	m = 998244353
	e = m - 2
	while e > 0:
		if e % 2 == 1:
			x = x * y % m
		y = y * y % m
		e >>= 1
	return x
[m, n, k] = input().split()
m = int(m)
n = int(n)
k = int(k)
if m == 1:
	x = (n - 1) * (k - 1) + k
	print(f(x, k))
elif n == 1:
	print(f(2 * k - 1, k))
else:
	x = 2 * n * k * k * k - k * k * (3 * n - 2) + n - 1
	print(f(x, k * k * k))


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True

def modinv(A, C):
	if A == 0:
		return (0, 1)
	(x1, y1) = modinv(C % A, A)
	x = y1 - C // A * x1
	y = x1
	return (x, y)
(m, n, k) = mp()
if m == 1:
	num = n * k - n + 1
	den = k
else:
	num = pow(k, 2, mod2) * (2 * k - 1) + (n - 1) * (2 * pow(k - 1, 3, mod2) + 3 * pow(k - 1, 2, mod2))
	den = pow(k, 3, mod2)
(x, y) = modinv(den, mod2)
x = x + mod2 if x < 0 else x
print(num % mod2 * x % mod2)


p = 998244353

def inverse(x):
	return pow(x, p - 2, p)

def e_single(N, K):
	ret = 1 + (N - 1) * (K - 1) * inverse(K)
	ret = ret % p
	return ret

def e_double(N, K):
	c0 = pow(inverse(K), 3, p)
	c1 = (K - 1) * c0 % p
	c2 = (K - 1) * (K - 2) * c0 % p
	c3 = ((K - 1) * (K - 2) * (K - 2) + (K - 1) * (K - 1)) * c0 % p
	p0 = (c0 + 3 * c1) % p
	p1 = (3 * c1 + 3 * c2) % p
	p2 = (c2 + c3) % p
	e = e_single(2, K)
	for _ in range(N - 1):
		e = (e * p0 + (e + 1) * p1 + (e + 2) * p2) % p
	return e

def solve(M, N, K):
	if M == 1:
		return e_single(N, K)
	elif M == 2:
		return e_double(N, K)
	else:
		return 1 / 0

def io():
	(M, N, K) = map(int, input().split())
	print(solve(M, N, K))
io()


from sys import stdin, stdout
input = stdin.readline
m = 998244353

def check(arr):
	global n, count
	mat = [arr[:n], arr[n:]]
	seen = {}
	for j in range(n):
		for i in range(2):
			seen[i, j] = 0
	for i in range(2):
		for j in range(n):
			if seen[i, j]:
				continue
			count = (count + 1) % m
			stack = []
			stack.append((i, j))
			while len(stack):
				start = stack.pop()
				seen[start] = 1
				x = start[0]
				y = start[1]
				if x == 0:
					if seen[x + 1, y] == 0 and mat[x + 1][y] == mat[x][y]:
						stack.append((x + 1, y))
				elif seen[x - 1, y] == 0 and mat[x - 1][y] == mat[x][y]:
					stack.append((x - 1, y))
				if y - 1 >= 0:
					if seen[x, y - 1] == 0 and mat[x][y - 1] == mat[x][y]:
						stack.append((x, y - 1))
				if y + 1 < n:
					if seen[x, y + 1] == 0 and mat[x][y + 1] == mat[x][y]:
						stack.append((x, y + 1))

def Backtrack(arr, i):
	global n, k
	if i == 2 * n:
		check(arr)
		return
	for j in range(1, k + 1):
		arr[i] = j
		Backtrack(arr, i + 1)
t = 1
for _ in range(t):
	(x, n, k) = map(int, input().split())
	count = 0
	if x == 2:
		sigma = 0
		p1 = 1 + 2 * (2 * k - 2)
		p1 %= m
		p1 += (k ** 2 - 2 * k + 1 - k + 1) * 3
		p1 %= m
		p1 += (k - 1) * 2
		p1 %= m
		p2 = 2
		p2 += (2 * k - 2 - 2) * 3
		p2 %= m
		p2 += 2 * 2
		p2 += (k ** 2 - 2 * k + 1 - k + 2) * 4
		p2 %= m
		p2 += (k - 2) * 3
		p2 %= m
		for i in range(1, n):
			temp = 0
			sigma = ((pow(k, 2, m) - k) % m * p2 % m + k * p1 % m) % m
			v1 = p2 * (2 * k - 2)
			v1 %= m
			v1 += p1
			v1 %= m
			v1 += (k * k - 2 * k + 1 - k + 1) % m * (p2 + pow(k, 2 * i, m)) % m % m
			v1 += (k - 1) * (p1 + pow(k, 2 * i, m)) % m % m
			v2 = p2
			v2 += (2 * k - 4) * (p2 + pow(k, 2 * i, m)) % m % m
			v2 += 2 * (p1 + pow(k, 2 * i, m)) % m
			v2 += (k * k - 2 * k + 1 - k + 2) % m * (p2 + 2 * pow(k, 2 * i, m)) % m % m
			v2 += (k - 2) * (p1 + 2 * pow(k, 2 * i, m)) % m % m
			p1 = v1
			p2 = v2
		p = sigma
		q = pow(k, 2 * n, m)
		ans = p * pow(q, m - 2, m) % m
		print(ans)
	else:
		p = 1
		term1 = 1
		term2 = 1
		pivot = n - 1
		d = 1
		for i in range(n - 1):
			term1 = term1 * (k - 1) % m
			term2 = term2 * pivot % m
			term2 = term2 * pow(d, m - 2, m) % m
			pivot -= 1
			d += 1
			p = (p + term1 * term2 * (i + 2) % m) % m
		p = p * k % m
		q = pow(k, n, m)
		ans = p * pow(q, m - 2, m) % m
		print(ans)


(M, N, K) = map(int, input().split())
P = 998244353

def main():
	Kminus1tothe = [1] * (2 * N)
	Ktotheminus = [1] * (2 * N)
	Kinv = invert_mod(K, P)
	for i in range(1, 2 * N):
		Kminus1tothe[i] = (K - 1) * Kminus1tothe[i - 1] % P
		Ktotheminus[i] = Kinv * Ktotheminus[i - 1] % P
	accum = 1 + (N - 1) * Kminus1tothe[1] * Ktotheminus[1]
	if M == 2:
		for l in range(1, N - 1):
			accum += (N - 1 - l) * Kminus1tothe[l + 2] * Ktotheminus[2 * l + 1]
		for l in range(1, N):
			accum += 2 * Kminus1tothe[l + 1] * Ktotheminus[2 * l]
		accum += Kminus1tothe[N] * Ktotheminus[2 * N - 1]
		for l in range(3, N + 1):
			accum -= (N - l + 1) * Kminus1tothe[l - 2] * Ktotheminus[2 * l - 1]
	print(accum % P)

def bezout_solver(a, b):
	if a < b:
		(y, x) = bezout_solver(b, a)
		return (x, y)
	elif b == 0:
		return (1, 0)
	(q, r) = (a // b, a % b)
	(z, x) = bezout_solver(b, r)
	return (x, z - q * x)

def invert_mod(num, modulus):
	return bezout_solver(modulus, num)[1] % modulus
main()


(m, n, k) = (int(x) for x in input().split())
p = 998244353

def ipow(a, b):
	c = 1
	while b:
		if b % 2:
			c = c * a % p
		b = b // 2
		a = a * a % p
	return c
kin = ipow(k, p - 2)
if m == 1:
	print((p + n - (n - 1) * kin % p) % p)
else:
	print((p + 2 * n + (n - 1) * ipow(kin, 3) - (3 * n - 2) * kin % p) % p)


import sys
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def gtc(tc, ans):
	print('Case #' + str(tc) + ':', ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = 1
uu = t

def nary(n, m):
	if n == 0:
		return '0'
	nums = []
	while n:
		(n, r) = divmod(n, m)
		nums.append(str(r))
	return ''.join(reversed(nums))
while t > 0:
	t -= 1
	(m, n, k) = mi()
	mod = 998244353

	def inv(m):
		return invv[m]

	def poww(k, n, mod):
		return pw[n]
	if m == 1:
		if n == 1:
			print(1)
			continue
		ans = 0
		for i in range(1, n + 1):
			ns = n - i + 1
			if i != n:
				if i < n - 1:
					ans = (ans + (ns - 2) * pow(k, n - i - 2, mod) * k * (k - 1) ** 2) % mod
				ans = (ans + 2 * pow(k, n - i - 1, mod) * k * (k - 1)) % mod
			else:
				ans += k
		print(ans * pow(pow(k, n, mod), mod - 2, mod) % mod)
	if m == 2:
		if k == 1:
			print(1)
			continue
		dp = [[0] * 4 for i in range(n)]
		ans = 0
		N = n
		n = 2 * n
		pw = [1] * (n + 1)
		for i in range(1, n + 1):
			pw[i] = pw[i - 1] * k % mod
		invv = {}
		invv[k * (k - 1)] = pow(k * (k - 1), mod - 2, mod)
		for i in range(1, 4):
			invv[k ** i] = pow(k ** i, mod - 2, mod)
			invv[(k - 1) ** i] = pow((k - 1) ** i, mod - 2, mod)
		for i in range(N):
			if i == 0:
				if N == 1:
					dp[i][1] = k * (k - 1) % mod
					dp[i][2] = k * (k - 1) % mod
					dp[i][3] = k % mod
				else:
					dp[i][1] = poww(k, n - 2, mod) * (k - 1) ** 2 % mod
					dp[i][2] = poww(k, n - 2, mod) * (k - 1) ** 2 % mod
					dp[i][3] = poww(k, n - 3, mod) * (k - 1) ** 2 % mod
			elif i == N - 1:
				dp[i][1] = poww(k, n - 2, mod) * (k - 1) ** 2 % mod + dp[i - 1][1] * inv(k) % mod + dp[i - 1][3] * inv(k - 1) % mod
				dp[i][1] %= mod
				dp[i][2] = poww(k, n - 2, mod) * (k - 1) ** 2 % mod + dp[i - 1][2] * inv(k) % mod + dp[i - 1][3] * inv(k - 1) % mod
				dp[i][2] %= mod
				dp[i][3] = poww(k, n - 3, mod) * (k - 1) ** 2 % mod + dp[i - 1][3] * inv((k - 1) ** 2) % mod + (dp[i - 1][1] + dp[i - 1][2]) * inv(k * (k - 1)) % mod
				dp[i][3] %= mod
			else:
				dp[i][1] = poww(k, n - 3, mod) * (k - 1) ** 3 % mod + dp[i - 1][1] * inv(k ** 2) * (k - 1) + dp[i - 1][3] * inv(k)
				dp[i][1] %= mod
				dp[i][2] = poww(k, n - 3, mod) * (k - 1) ** 3 % mod + dp[i - 1][2] * inv(k ** 2) * (k - 1) % mod + dp[i - 1][3] * inv(k) % mod
				dp[i][2] %= mod
				dp[i][3] = poww(k, n - 5, mod) * (k - 1) ** 4 % mod + dp[i - 1][3] * inv(k ** 2) % mod + (dp[i - 1][1] + dp[i - 1][2]) % mod * (k - 1) * inv(k ** 3) % mod
			ans += sum(dp[i])
			ans %= mod
		print(ans * pow(pow(k, n, mod), mod - 2, mod) % mod)


mod = 998244353

def modinv(a, p):
	return pow(a, p - 2, p)
(M, N, K) = map(int, input().split())
if M == 1:
	s = (K + (N - 1) * (K - 1)) % mod
	print(s * modinv(K, mod) % mod)
else:
	s = (2 * K * K - 1 + (2 * K * K * K - 3 * K * K + 1) * N) % mod
	print(s * modinv(K * K * K, mod) % mod)


import sys
input = sys.stdin.readline

def inv(x):
	return pow(x, 998244351, 998244353)
l = input().split()
m = int(l[0])
n = int(l[1])
k = int(l[2])
if m == 1:
	z = (n - 1) * (k - 1)
	z += k
	z %= 998244353
	z = z * inv(k)
	z %= 998244353
	print(z)
	quit()
mod = 998244353
z = 2 * k - 1
z = z * inv(k)
z %= mod
diff = 2 * k * k * k
diff %= mod
diff -= 3 * k * k
diff %= mod
diff += 1
diff %= mod
lol = k * k * k
lol %= mod
diff = diff * inv(lol)
z += (n - 1) * diff
z %= mod
print(z)


(m, n, k) = map(int, input().split())
mod = 998244353
if m == 1:
	print((n * k - n + 1) * pow(k, mod - 2, mod) % mod)
else:
	a = (2 * k - 1) * k * k
	d = 2 * (k - 1) ** 3 + 3 * (k - 1) ** 2
	num = a + (n - 1) * d
	denom = k ** 3
	print(num * pow(denom, mod - 2, mod) % mod)