P8558 Darkness (Darkness).

Ling is searching for Mio in a dark three-dimensional space. This space can be represented as $\{(x,y,z) \mid x \in[0,A],y \in [0,B],z\in [0,C] \}$. Ling initially stands at $(A,B,C)$, and Mio stands at $(0,0,0)$. Suppose Ling is at $(x,y,z)$. Each time she moves, she tries to move **uniformly at random** to $(x-1,y,z)$, or $(x,y-1,z)$, or $(x,y,z-1)$. The outer boundary of this space is made of walls and cannot be passed through. Because it is very dark, Ling does not know whether she has reached a wall. That is, when she randomly chooses one of the three directions to try to move, she may hit a wall. Ling wants to know the expected value of the $k$-th power of the “Manhattan distance to Mio (in this problem, it is the sum of the $x,y,z$ coordinates)” at the moment she hits a wall for the first time. You only need to output the result modulo $998244353$.

Input one line with four positive integers $A,B,C,k$.

Output one line with one integer, representing the answer.

[Sample $1$ Explanation.] The table below lists the probability of reaching each position and hitting a wall there: | $(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$ | You can see that only at these $7$ positions is it possible to hit a wall. From this, the expected value is $\dfrac{10}{9}$, which is $443664158$ modulo $998244353$. [Sample $2,3$ Explanation.] Here you need to compute the expected value of the square of the distance. The actual answers are $\dfrac{30083}{2187}$ and $\dfrac{22748643655}{387420489}$, respectively. [Constraints.] **This problem uses bundled testdata.** Subtask 1 (8 pts): $1\le A,B,C,k\le 6$. Subtask 2 (19 pts): $1\le A,B,C \le 100$. Subtask 3 (13 pts): $k=1$. Subtask 4 (23 pts): $1\le A,B,C,k \le 10^5$. Subtask 5 (37 pts): no special restrictions. For $100\%$ of the testdata, $1\le A,B,C \le 5\times 10^6$, $1\le k \le 10^7$. [Hint.] For a discrete random variable $X$, let the probability that it takes value $k$ be $P_k$. Then the expected value of $X$ is defined as: $$\sum_k kP_k$$ For a rational number $a/b$ ($a,b$ are both positive integers), if an integer $r$ satisfies $r\in[0,p-1]$ and $rb \equiv a \pmod p$, then $r$ is the result of $a/b$ modulo $p$. Translated by ChatGPT 5