Background

Bob loves segment trees.

Problem Description

If you are not familiar with segment trees, refer to the definition in the Notes/Hints section.

Bob has received a sequence \(a_{1,2,\cdots,n}\) of length \(n\), initially filled with zeros.

Bob then performs \(m\) range addition operations. Each operation randomly selects one of the \(\dfrac{n(n+1)}{2}\) subintervals of \([1,n]\) with equal probability and adds a random integer from \([-1, V]\) to it.

After \(m\) operations, Bob needs to determine the value at each position.

Since Bob loves segment trees, he skillfully constructs a segment tree on \([1,n]\) to solve this problem, using lazy tags to handle range additions.

While coding, Bob came up with two methods to reduce the number of \(\mathrm{Pushdown}\) (propagating lazy tags) operations:

• Do not \(\mathrm{Pushdown}\) during modifications, and perform \(\mathrm{Pushdown}\) all at once at the end (i.e., the \(\mathrm{Pushall}\) function).

• When \(\mathrm{Pushall}\) reaches a node, if the node's lazy tag is \(0\), do not \(\mathrm{Pushdown}\).

Now, Bob wants to know the expected number of \(\mathrm{Pushdown}\) operations, but he doesn't know how to calculate it, so he asks you for help.

Below is the pseudocode for Bob's segment tree (where tag array represents lazy tags):

\[ \begin{array}{l} \mathrm{pushdown\_counter} \leftarrow 0 \\ \\ \textbf{function } \mathrm{Update(Node}, l, r, ql, qr, Delta) \\ \qquad \textbf{if } [l, r] \cap [ql, qr] = \varnothing \textbf{ then} \\ \qquad \qquad \textbf{return} \\ \qquad \textbf{end if} \\ \qquad \textbf{if } [l, r] \subseteq [ql, qr] \textbf{ then} \\ \qquad \qquad \mathrm{tag[Node]} \leftarrow \mathrm{tag[Node]} + Delta \\ \qquad \qquad \textbf{return} \\ \qquad \textbf{end if} \\ \qquad mid \leftarrow \lfloor \dfrac{l+r}{2} \rfloor \\ \qquad \mathrm{Update(LeftChild}, l, mid, ql, qr, Delta) \\ \qquad \mathrm{Update(RightChild}, mid+1, r, ql, qr, Delta) \\ \textbf{end function} \\ \\ \textbf{function } \mathrm{Pushdown(Node)} \\ \qquad \mathrm{tag[LeftChild]} \leftarrow \mathrm{tag[LeftChild]} + \mathrm{tag[Node]} \\ \qquad \mathrm{tag[RightChild]} \leftarrow \mathrm{tag[RightChild]} + \mathrm{tag[Node]} \\ \qquad \mathrm{pushdown\_counter} \leftarrow \mathrm{pushdown\_counter} + 1 \\ \textbf{end function} \\ \\ \textbf{function } \mathrm{Pushall(Node}, l, r) \\ \qquad \textbf{if } \mathrm{Node\ is\ Leaf} \textbf{ then} \\ \qquad \qquad \textbf{return} \\ \qquad \textbf{end if} \\ \qquad \textbf{if } \mathrm{tag[Node]} \neq 0 \textbf{ then} \\ \qquad \qquad \mathrm{Pushdown(Node)} \\ \qquad \textbf{end if} \\ \qquad mid \leftarrow \lfloor \dfrac{l+r}{2} \rfloor \\ \qquad \mathrm{Pushall(LeftChild}, l, mid) \\ \qquad \mathrm{Pushall(RightChild}, mid+1, r) \\ \textbf{end function} \end{array} \]

In other words, you need to help Bob calculate the expected value of pushdown_counter.

The answer should be modulo \(998244353\).

Input Format

A single line containing three integers \(n, m, V\).

Output Format

A single integer, the expected number of \(\mathrm{Pushdown}\) operations modulo \(998244353\).

Sample Input and Output

Sample Input #1

2 1 0

Sample Output #1

166374059

Sample Input #2

2 2 1

Sample Output #2

813384288

Sample Input #3

3 2 1

Sample Output #3

462150164

Sample Input #4

100 114 514

Sample Output #4

718571152

Notes/Hints

[Sample Explanation #1]

The segment tree has only 3 nodes: \([1,2], [1,1], [2,2]\).

Only the node \([1,2]\) can potentially \(\mathrm{Pushdown}\).

When the operation is \(\mathrm{Update(1,2,-1)}\), the root node's lazy tag is \(-1\), and \(\mathrm{Pushall}\) at the root node will \(\mathrm{Pushdown}\); whereas \(\mathrm{Update(1,2,0)}\) results in the root node's lazy tag being \(0\), so no \(\mathrm{Pushdown}\).

The other 4 operations place the lazy tag on leaf nodes, i.e., \(\mathrm{Update(1,1,-1)}, \mathrm{Update(1,1,0)}, \mathrm{Update(2,2,-1)}, \mathrm{Update(2,2,0)}\), which do not \(\mathrm{Pushdown}\).

Thus, out of 6 possible scenarios, only 1 can \(\mathrm{Pushdown}\), resulting in an expected count of \(\dfrac{1}{6}\).

[Sample Explanation #2]

Due to the large number of scenarios, only one is explained.

If the two operations performed are \(\mathrm{Update(1,2,-1)}\) and \(\mathrm{Update(1,2,1)}\), since the root node's lazy tag is \(0\) at \(\mathrm{Pushall}\), it still will not \(\mathrm{Pushdown}\).

[Data Range]

This problem uses subtask testing.

For 100% of the data, \(1 \le n \le 10^5\), \(1 \le m \le 10^5\), \(-1 \le V \le 998244350\).

[Segment Tree Definition]

A segment tree is a binary tree where each node records a segment. The root node records the segment \([1, n]\). For each node, if it records the segment \([l, r]\) and \(l \neq r\), let \(m = \lfloor \dfrac{l+r}{2} \rfloor\), then its left and right child nodes record the segments \([l, m]\) and \([m+1, r]\), respectively; if \(l = r\), it is a leaf node.

见题面 Input 部分

见题面 Output 部分