Problem Description

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 Format

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

Output Format

Output one line with one integer, representing the answer.

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

Hint

[Sample $1$ Explanation.]

The table below lists the probability of reaching each position and hitting a wall there:

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:

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