201115: [AtCoder]ARC111 F - Do you like query problems?
Description
Score : $1000$ points
Problem Statement
Yosupo loves query problems. He made the following problem:
A Query Problem
We have an integer sequence of length $N$: $a_1,\ldots,a_N$. Initially, $a_i = 0 (1 \leq i \leq N)$. We also have a variable $ans$, which is initially $0$. Here, you will be given $Q$ queries of the following forms:
Type 1:
$t_i (=1)$ $l_i$ $r_i$ $v_i$
For each $j = l_i,\ldots,r_i$, $a_j := \min(a_j,v_i)$.
Type 2:
$t_i (=2)$ $l_i$ $r_i$ $v_i$
For each $j = l_i,\ldots,r_i$, $a_j := \max(a_j,v_i)$.
Type 3:
$t_i (=3)$ $l_i$ $r_i$
Compute $a_{l_i} + \ldots + a_{r_i}$ and add the result to $ans$.
Print the final value of $ans$.
Here, for each query, $1$ $\leq$ $l_i$ $\leq$ $r_i$ $\leq$ $N$ holds. Additionally, for Type 1 and 2, $0$ $\leq$ $v_i$ $\leq$ $M-1$ holds.
Maroon saw this problem, thought it was too easy, and came up with the following problem:
Query Problems
Given are positive integers $N,M,Q$. There are $( \frac{(N+1)N}{2} \cdot (M+M+1) )^Q$ valid inputs for "A Query Problem". Find the sum of outputs over all those inputs, modulo $998{,}244{,}353$.
Find it.
Constraints
- $1 \leq N,M,Q \leq 200000$
- All numbers in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $Q$
Output
Print the answer.
Sample Input 1
1 2 2
Sample Output 1
1
There are $25$ valid inputs, and just one of them - shown below - results in a positive value of $ans$.
$t_1 = 2, l_1 = 1, r_1 = 1, v_1 = 1, t_2 = 3, l_2 = 1, r_2 = 1$
$ans$ will be $1$ in this case, so the answer is $1$.
Sample Input 2
3 1 4
Sample Output 2
0
Sample Input 3
111 112 113
Sample Output 3
451848306