#abc289h. [abc289_h]Trio

[abc289_h]Trio

問題文

数直線上に人 11, 人 22, 人 33 がいます。時刻 00 の時点で、人 11 は地点 AA に、人 22 は地点 BB に、人 33 は地点 CC にいます。
ここで A,B,CA, B, C はすべて整数で、AequivBequivCpmod2A \\equiv B \\equiv C \\pmod{2} が成り立ちます。

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

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

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

制約

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

入力

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

AA BB CC TT

出力

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


入力例 1

1 1 3 1

出力例 1

873463809

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


入力例 2

0 0 0 0

出力例 2

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


入力例 3

0 2 8 9

出力例 3

744570476

入力例 4

47717 21993 74147 76720

出力例 4

844927176