Background

Bob likes segment trees.

Problem Description

If you do not know what a segment tree is, you can read the definition in the Hint section.

Bob is given a sequence $a_{1,2,\cdots,n}$ of length $n$, initially all $0$.

Then Bob performs $m$ range-add operations. Each operation randomly selects one sub-interval uniformly from all $\dfrac{n(n+1)}{2}$ sub-intervals of $[1,n]$ to apply the operation. The added value each time is a uniformly random integer in $[-1,V]$.

After all $m$ operations, you need to obtain the value at every position.

Since Bob likes segment trees, he quickly wrote a segment tree over $[1,n]$ to solve this problem, using lazy tags to handle range addition.

While coding, Bob suddenly thought of two ways to reduce the number of $\mathrm{Pushdown}$ operations (pushing down lazy tags):

• Do not $\mathrm{Pushdown}$ during updates, and do all $\mathrm{Pushdown}$ operations at the end at once (i.e., the $\mathrm{Pushall}$ function).

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

Now Bob wants to know the expected number of $\mathrm{Pushdown}$ operations, but he cannot compute it, so he asks you.

Below is the segment tree pseudocode written by Bob (the array tag stores lazy tags):

$\displaystyle \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 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 tag[LeftChild]+tag[Node]}\\ \qquad \mathrm{tag[RightChild]\leftarrow tag[RightChild]+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] \not= 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 compute the expected value of pushdown_counter.

Output the answer modulo $998244353$.

Input Format

One line with three integers $n,m,V$.

Output Format

One integer: the expected number of $\mathrm{Pushdown}$ operations modulo $998244353$.

2 1 0

166374059

2 2 1

813384288

3 2 1

462150164

100 114 514

718571152

Hint

Sample Explanation #1.

The whole segment tree has only $3$ nodes: $[1,2],[1,1],[2,2]$.

Only the node $[1,2]$ may perform $\mathrm{Pushdown}$.

When the operation is $\mathrm{Update(1,2,-1)}$, the root node's lazy tag is $-1$, so during $\mathrm{Pushall}$ it will $\mathrm{Pushdown}$ at the root; while after $\mathrm{Update(1,2,0)}$, since the root node's lazy tag is $0$, it will not $\mathrm{Pushdown}$.

The other $4$ operations all 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)}$, so they will not $\mathrm{Pushdown}$.

Therefore, among $6$ total cases, only $1$ case can $\mathrm{Pushdown}$, so the expected number is $\dfrac{1}{6}$.

Sample Explanation #2.

Since there are too many cases, they are not explained one by one; only one case is explained.

If the two executed operations are $\mathrm{Update(1,2,-1)},\mathrm{Update(1,2,1)}$, then the root node's lazy tag is $0$, so during $\mathrm{Pushall}$ it still will not $\mathrm{Pushdown}$.

Constraints.

This problem uses bundled testdata.

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

Definition of a Segment Tree.

A segment tree is a binary tree where each node stores a segment. The root node stores $[1,n]$. For each node, if the segment it stores is $[l,r]$ and $l\not= r$, let $m = \lfloor \dfrac{l+r}{2} \rfloor$, then its left and right child nodes store $[l,m]$ and $[m+1,r]$, respectively. If $l=r$, then it is a leaf node.

Translated by ChatGPT 5