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 starts at the coordinate $(A,B,C)$ and Mio is at $(0,0,0)$. Assuming Ling is at $(x,y,z)$, she will uniformly randomly attempt to move to $(x-1,y,z)$, $(x,y-1,z)$, or $(x,y,z-1)$.

The perimeter of this space is walls that cannot be passed through. Due to the darkness, Ling does not know if she has reached the wall. That is, when randomly choosing one of the three directions to attempt to move, she may hit the wall.

Ling wants to know the expected value of the $k$-th power of the "Manhattan distance to Mio (which in this case is the sum of the $x, y, z$ coordinates)" when she first hits the wall.

You only need to find the result modulo $998244353$.

Input Format

Input consists of four positive integers $A, B, C, k$ on a single line.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

1 1 1 1

Sample Output #1

443664158

Sample Input #2

2 3 4 2

Sample Output #2

128260948

Sample Input #3

4 6 9 2

Sample Output #3

622775535

Sample Input #4

58 88 133 233

Sample Output #4

128518400

Sample Input #5

114514 1919810 4999231 8214898

Sample Output #5

823989766

Notes

For sample 1, the table below lists the probabilities of reaching each position and hitting the wall:

It can be seen that there is a possibility of hitting the wall at these 7 positions. From this, the expected value is calculated to be $\dfrac{10}{9}$, which modulo $998244353$ is $443664158$.

For samples 2 and 3, the expected values of the square of the distance are $\dfrac{30083}{2187}$ and $\dfrac{22748643655}{387420489}$ respectively.

Data Range

This problem uses batched testing.

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): No special restrictions.

For $100\%$ of the data, $1\le A,B,C \le 5\times 10^6$, $1\le k \le 10^7$.

Hints

For a discrete random variable $X$, let $P_k$ be the probability that $X$ takes the value $k$. Then the expected value of $X$ is defined as:

$$\sum_k kP_k$$

For a rational number $a/b$ (where $a, b$ are positive integers), if an integer $r$ satisfies $r\in[0, p-1]$ and $\equiv a \pmod p$, then $r$ is the result of $a/b$ modulo $p$.

见题面 Input 部分

见题面 Output 部分