题目描述

铃在一个黑暗的三维空间内寻找澪。这个空间可以表示为 $\{(x,y,z) \mid x \in[0,A],y \in [0,B],z\in [0,C] \}$。铃初始站在坐标为 $(A,B,C)$ 处，澪站在 $(0,0,0)$ 处。假设铃在 $(x,y,z)$ 处，她每次移动会均匀随机地尝试移动到 $(x-1,y,z)$ 或 $(x,y-1,z)$ 或 $(x,y,z-1)$。

这个空间的外围是墙壁，不可穿过。由于空间内很暗，铃并不知道自己是否走到了墙边。也就是说，她在随机选择三种方向尝试移动时，有可能撞在墙上。

铃想要知道，自己在第一次撞墙时，「到澪的曼哈顿距离（在本题中的情况就是 $x,y,z$ 坐标之和）」的 $k$ 次方的期望值。

你只需要求出答案对 $998244353$ 取模的结果。

输入格式

输入一行四个正整数 $A,B,C,k$。

输出格式

输出一行一个整数表示答案。

1 1 1 1

443664158

2 3 4 2

128260948

4 6 9 2

622775535

58 88 133 233

128518400

114514 1919810 4999231 8214898

823989766

提示

【样例 $1$ 解释】

下表列出了走到各处并撞到墙的概率：

$(0,0,0)$	$(1,0,0)$	$(0,1,0)$	$(0,0,1)$	$(1,1,0)$	$(1,0,1)$	$(0,1,1)$
$2/9$	$4/27$			$1/9$

可以发现只有在这 $7$ 个位置有可能撞到墙。由此算出期望值为 $\dfrac{10}{9}$，在模 $998244353$ 意义下为 $443664158$。

【样例 $2,3$ 解释】

这里要算的都是距离的平方的期望。实际答案分别为 $\dfrac{30083}{2187}$ 和 $\dfrac{22748643655}{387420489}$。

【数据范围】

本题采用捆绑测试。

Subtask1（8 pts）：$1\le A,B,C,k\le 6$；
Subtask2（19 pts）：$1\le A,B,C \le 100$；
Subtask3（13 pts）：$k=1$；
Subtask4（23 pts）：$1\le A,B,C,k \le 10^5$；
Subtask5（37 pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le A,B,C \le 5\times 10^6$，$1\le k \le 10^7$。

【提示】

对于离散随机变量 $X$，其取值等于 $k$ 的概率设为 $P_k$，则 $X$ 的期望值定义为：

$$\sum_k kP_k$$

对于有理数 $a/b$（$a,b$ 均为正整数），若整数 $r$ 满足 $r\in[0,p-1]$ 且 $rb \equiv a \pmod p$，则 $r$ 就是 $a/b$ 对 $p$ 取模的结果。