問題文

数直線上に人 $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$ で計算してください。

有理数 $\\text{mod }998244353$ とは 求める確率は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な $2$ つの整数 $P$, $Q$ を用いて $\\frac{P}{Q}$ と表したとき、$R \\times Q \\equiv P\\pmod{998244353}$ かつ $0 \\leq R \\lt 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $R$ を求めてください。

制約

• $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 1 3 1

出力例 1

873463809

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

入力例 2

0 0 0 0

出力例 2

1

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

入力例 3

0 2 8 9

出力例 3

744570476

入力例 4

47717 21993 74147 76720

出力例 4

844927176