黑暗（Darkness）

铃在一个黑暗的三维空间内寻找澪。这个空间可以表示为 $\{(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$ | $4/27$ | $4/27$ | $1/9$ | $1/9$ | $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$ 取模的结果。