Expected Number of Pushdowns in Lazy Segment Tree

Bob has a sequence (a_{1,2,\cdots,n}) of length (n) initially filled with zeros. He then performs (m) operations; in each operation, he chooses uniformly at random one of the (\frac{n(n+1)}{2}) subintervals of ([1,n]) and adds an integer chosen uniformly at random from the set ([-1,V]) (that is, all integers between (-1) and (V), inclusive).

After all operations, Bob constructs a segment tree on the interval ([1,n]) (using lazy propagation for range increments). He then applies a function called Pushall to push down all lazy tags. The pseudocode of the segment tree is given below (the array tag contains the lazy tags):

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

When Pushall is run, it calls (Pushdown) at an internal node if and only if its lazy tag is nonzero. Bob wonders: what is the expected value of (\mathrm{pushdown_counter}) after all operations, computed modulo (998244353)?

Note: A node in the segment tree is built in the standard recursive way: for an interval ([l,r]), if (l=r) it is a leaf; otherwise, it is an internal node with children covering ([l,\lfloor\frac{l+r}{2}\rfloor]) and ([\lfloor\frac{l+r}{2}\rfloor+1, r]) respectively.

The effect of the (m) operations is that, for each internal node corresponding to an interval ([l,r]) (with (l<r)), its lazy tag becomes the sum of contributions from those updates that fully cover ([l,r]). An update contributes (\Delta) (chosen uniformly from ([-1,V])) if the chosen subinterval completely covers ([l,r]). Therefore, for a node corresponding to ([l,r]), the probability that a particular update contributes a nonzero value is [ \displaystyle r_{l,r} = \frac{2l,(n-r+1)}{n(n+1)} \cdot \frac{V+1}{V+2}. ] If the final lazy tag (the sum of contributions) is nonzero then Pushall will cause one pushdown at that node; otherwise, it will not. The expected pushdown count is the sum, over all internal nodes in the segment tree, of the probability that the final lazy tag is nonzero.

Furthermore, if we define for a given internal node and one update the following generating function for its contribution (when the update affects the node): [ f(x) = (1-r_{l,r}) + \frac{r_{l,r}}{V+1}\Bigl(x^{-1} + x^1 + x^2 + \cdots + x^V\Bigr), ] then after (m) independent updates the probability that the total contribution is zero is the coefficient of (x^0) in (f(x)^m).

Your task is to compute the expected number of pushdowns over all internal nodes modulo (998244353).

inputFormat

The input consists of a single line containing three integers (n), (m), and (V), where (n) is the length of the sequence, (m) is the number of operations, and (V) defines the range ([-1,V]) from which update increments are drawn.

outputFormat

Output a single integer: the expected number of pushdowns (i.e. the expected value of (\mathrm{pushdown_counter})) modulo (998244353).

sample

3 1 1

332748118