配点 : $600$ 点

問題文

数直線上に人 $1$, 人 $2$, 人 $3$ がいます。時刻 $0$ の時点で、人 $1$ は地点 $A$ に、人 $2$ は地点 $B$ に、人 $3$ は地点 $C$ にいます。 ここで $A, B, C$ はすべて整数で、$A \equiv B \equiv C \pmod{2}$ が成り立ちます。

$3$ 人は時刻 $0$ からランダムウォークを行います。詳しく説明すると、時刻 $t$ ( $t$ は非負整数 ) の時点で地点 $x$ にいる人は、時刻 $t+1$ に地点 $x-1$ と地点 $x+1$ のいずれか一方に等確率で移動します。(すべての移動する方向の選択は、ランダムかつ独立です。)

このとき、時刻 $0$ 以降で、時刻 $T$ に初めて $3$ 人が同じ地点にいる状態になる確率を $\text{mod } 998244353$ で計算してください。

制約

• $0 \leq A, B, C, T \leq 10^5$
• $A \equiv B \equiv C \pmod{2}$
• $A, B, C, T$ は整数

入力

入力は以下の形式で標準入力から与えられる。

$A$ $B$ $C$ $T$

出力

時刻 $T$ に初めて $3$ 人が同じ地点にいる状態になる確率を $\text{mod } 998244353$ で計算して、答えを出力せよ。

1 1 3 1

873463809

時刻 $1$ に初めて $3$ 人が同じ地点にいる状態になる確率は $\frac{1}{8}$ です。$873463809 \times 8 \equiv 1 \pmod{998244353}$ なので $873463809$ を出力します。

0 0 0 0

1

時刻 $0$ の時点ですでに $3$ 人が同じ地点にいる場合もあります。

0 2 8 9

744570476

47717 21993 74147 76720

844927176