問題文

yosupoくんはクエリの問題が大好きなので、次のような問題を作りました。

A Query Problem

長さ $N$ の整数列 $a_1,\\ldots,a_N$ があります。はじめは $a_i = 0 (1 \\leq i \\leq N)$ です。 また、$ans$ という変数があり、はじめは $ans = 0$ です。 ここに、次の形式のクエリが $Q$ 個来ます。

• クエリ1:

  • $t_i (=1)$ $l_i$ $r_i$ $v_i$

  • 各 $j = l_i,\\ldots,r_i$ に対して、$a_j := \\min(a_j,v_i)$

• クエリ2:

  • $t_i (=2)$ $l_i$ $r_i$ $v_i$

  • 各 $j = l_i,\\ldots,r_i$ に対して、$a_j := \\max(a_j,v_i)$

• クエリ3:

  • $t_i (=3)$ $l_i$ $r_i$

  • $a_{l_i} + \\ldots + a_{r_i}$ を計算して、$ans$ に足す

最終的な $ans$ の値を出力してください。

ただし、各クエリについて、$1$ $\\leq$ $l_i$ $\\leq$ $r_i$ $\\leq$ $N$ が、さらにクエリ1,2については $0$ $\\leq$ $v_i$ $\\leq$ $M-1$ が成立する。

この問題を見たmaroonくんは簡単すぎると感じたため、次の問題を考えました。

Query Problems

正整数 $N,M,Q$ が与えられます。問題 "A Query Problem" に対する入力は $( \\frac{(N+1)N}{2} \\cdot (M+M+1) )^Q$ 通りありますが、それらに対する出力のすべての和を $998{,}244{,}353$ で割った余りを求めてください。

求めてください。

制約

• $1 \\leq N,M,Q \\leq 200000$
• 入力される数はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $Q$

出力

答えを出力せよ。

入力例 1

1 2 2

出力例 1

1

ありうる入力は $25$ 通りありますが、そのうち $ans$ が正になるような入力は、次の一通りです:

$t_1 = 2, l_1 = 1, r_1 = 1, v_1 = 1, t_2 = 3, l_2 = 1, r_2 = 1$

このとき $ans$ は $1$ になるので、答えは $1$ です。

入力例 2

3 1 4

出力例 2

0

入力例 3

111 112 113

出力例 3

451848306