Expected Manhattan Distance Power at First Wall Collision

In a dark three‐dimensional space, represented by [ {(x,y,z) \mid x\in[0,A],; y\in[0,B],; z\in[0,C]}, ] Rin starts at ((A,B,C)) and Mio is at ((0,0,0)). At any point ((x,y,z)), Rin chooses uniformly at random one of the three moves: to ((x-1,y,z)), ((x,y-1,z)), or ((x,y,z-1)). The boundaries of the space are walls that cannot be crossed. Since it is dark she does not know if she is at the boundary; that is, she might attempt a move that would hit a wall. The process stops at the very first time she collides with a wall (i.e. when a chosen move would take some coordinate below 0). At that moment, let (S=x+y+z) be her Manhattan distance from Mio. Given an integer (k\ge 0) the task is to compute the expected value of (S^k) modulo (998244353).

More formally, let (F(x,y,z)) denote the expected value (under the described random process) starting from state ((x,y,z)). Then for any state ((x,y,z)) the recurrence is [ F(x,y,z) = \frac{1}{3}\Bigl[(I{x=0}+I{y=0}+I{z=0}),(x+y+z)^k + \sum_{\substack{(x',y',z'):,\text{a valid move from}\,(x,y,z)}}F(x',y',z')\Bigr], ] with the understanding that a move is valid only if the corresponding coordinate is positive, and the process stops immediately when a move would result in a coordinate becoming negative. (For example, in state ((0,y,z)) the move in the (x)–direction is invalid and immediately causes a collision.)

You are given four integers (A, B, C, k) and must output the answer (F(A,B,C)) modulo (998244353).

Note: When (k=0) we define (0^0=1).

inputFormat

The input consists of a single line containing four integers A B C k, where 0 ≤ A,B,C ≤ (small enough for a recursive solution) and k ≥ 0.

outputFormat

Output a single integer: the expected value of the Manhattan distance (the sum of coordinates) raised to the power k at the time of the first collision with a wall, modulo 998244353.

sample

1 1 1 1

443664158