P7445 "EZEC-7" Segment Tree.

Bob likes segment trees.

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$.

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

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

**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.** | Subtask ID | $n\le$ | $m\le$ | $V$ | Score | Time Limit$\text{ / ms}$ | | :----: | :------------: | :------------: | :-----------------: | :----: | :--------: | | $1$ | $4$ | $4$ | $\le 2$ | $3$ | $500$ | | $2$ | $300$ | $300$ | $\le 300$ | $7$ | $500$ | | $3$ | $1000$ | $1000$ | $\le 1000$ | $10$ | $500$ | | $4$ | $300$ | $10^5$ | $=1000$ | $15$ | $2000$ | | $5$ | $10^5$ | $10^5$ | $\le 0$ | $10$ | $3000$ | | $6$ | $10^5$ | $10^5$ | $=1000$ | $15$ | $3000$ | | $7$ | $10^5$ | $10^5$ | $\le 998244350$ | $40$ | $3000$ | 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