题目背景

Bob 喜欢线段树。

题目描述

如果你不知道线段树，可以看 提示说明 中的定义。

Bob 得到了一个长度为 $n$ 的序列 $a_{1,2,\cdots,n}$，初始全为 $0$。

接着 Bob 进行了 $m$ 次区间加操作，每次操作会等概率地从 $[1,n]$ 的所有 $\dfrac{n(n+1)}{2}$ 个子区间中随机选择一个进行操作，每次加的数是 $[-1,V]$ 之间等概率随机的整数。

$m$ 次操作完之后要求出每一个位置的值。

由于 Bob 喜欢线段树，他熟练地打出一颗 $[1,n]$ 上的线段树来解决这个问题，使用懒惰标记来解决区间加的问题。

打代码的过程中 Bob 忽然想到了两个减小 $\mathrm{Pushdown}$（下传懒惰标记）次数的方法：

• 修改的时候不 $\mathrm{Pushdown}$，最后一次性 $\mathrm{Pushdown}$（即 $\mathrm{Pushall}$ 函数）。

• $\mathrm{Pushall}$ 到一个节点的时候，如果这个节点的懒惰标记为 $0$ 那么不 $\mathrm{Pushdown}$。

现在 Bob 想知道期望 $\mathrm{Pushdown}$ 次数，可是他不会算，于是来问你。

下面是 Bob 写的线段树伪代码（其中 tag 数组为懒惰标记）：

$ \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} $

换句话说，你要帮 Bob 求出 pushdown_counter 的期望值。

答案对 $998244353$ 取模。

输入格式

一行三个整数 $n,m,V$。

输出格式

一个整数，期望 $\mathrm{Pushdown}$ 次数对 $998244353$ 取模的结果。

2 1 0

166374059

2 2 1

813384288

3 2 1

462150164

100 114 514

718571152

提示

【样例解释 #1】

整颗线段树只有 $3$ 个节点：$[1,2],[1,1],[2,2]$。

只有节点 $[1,2]$ 可能 $\mathrm{Pushdown}$。

当操作为 $\mathrm{Update(1,2,-1)}$ 的时候，根节点的懒惰标记为 $-1$， $\mathrm{Pushall}$ 在根号节点会 $\mathrm{Pushdown}$；而 $\mathrm{Update(1,2,0)}$ 之后，由于根节点懒惰标记为 $0$ 不 $\mathrm{Pushdown}$。

其余 $4$ 种操作均把懒惰标记打在叶子节点，即 $\mathrm{Update(1,1,-1)},\mathrm{Update(1,1,0)},\mathrm{Update(2,2,-1)},\mathrm{Update(2,2,0)}$，不会 $\mathrm{Pushdown}$。

所以，总共 $6$ 种情况，能 $\mathrm{Pushdown}$ 的只有 $1$ 种，期望次数为 $\dfrac{1}{6}$。

【样例解释 #2】

由于情况过多，不一一解释，只解释一种情况。

如果执行的 $2$ 次操作分别为 $\mathrm{Update(1,2,-1)},\mathrm{Update(1,2,1)}$，由于这时候根节点的懒惰标记为 $0$，在 $\mathrm{Pushall}$ 的时候仍然不会 $\mathrm{Pushdown}$。

---

【数据范围】

本题采用捆绑测试。

子任务编号	$n\le$	$m\le$	$V$	分值	时间限制$\text{ / ms}$
$1$	$4$		$\le 2$	$3$	$500$
$2$	$300$		$\le 300$	$7$
$3$	$1000$		$\le 1000$	$10$
$4$	$300$	$10^5$	$=1000$	$15$	$2000$
$5$	$10^5$		$\le 0$	$10$	$3000$
$6$			$=1000$	$15$
$7$			$\le 998244350$	$40$

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le m \le 10^5$，$-1 \le V \le 998244350$。

---

【线段树定义】

线段树是一棵每个节点上都记录了一个线段的二叉树。根节点记录的线段是 $[1, n]$。对于每个节点，若它记录的线段是 $[l, r]$ 且 $l\not= r$，取 $m = \lfloor \dfrac{l+r}{2} \rfloor$，则它的左右儿子节点记录的线段分别是 $[l, m]$ 和 $[m+1,r]$；若 $l=r$，则它是叶子节点。