AT_arc111_f [ARC111F] Do you like query problems?

[problemUrl]: https://atcoder.jp/contests/arc111/tasks/arc111_f 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 $ で割った余りを求めてください。 - - - - - - 求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ Q $

答えを出力せよ。

### 制約 - $ 1\ \leq\ N,M,Q\ \leq\ 200000 $ - 入力される数はすべて整数 ### Sample Explanation 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 $ です。