問題文
数直線上に人 1, 人 2, 人 3 がいます。時刻 0 の時点で、人 1 は地点 A に、人 2 は地点 B に、人 3 は地点 C にいます。
ここで A,B,C はすべて整数で、AequivBequivCpmod2 が成り立ちます。
3 人は時刻 0 からランダムウォークを行います。詳しく説明すると、時刻 t ( t は非負整数 ) の時点で地点 x にいる人は、時刻 t+1 に地点 x−1 と地点 x+1 のいずれか一方に等確率で移動します。(すべての移動する方向の選択は、ランダムかつ独立です。)
このとき、時刻 0 以降で、時刻 T に初めて 3 人が同じ地点にいる状態になる確率を textmod998244353 で計算してください。
有理数 textmod998244353 とは 求める確率は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて fracPQ と表したとき、RtimesQequivPpmod998244353 かつ 0leqRlt998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。
制約
- 0leqA,B,C,Tleq105
- AequivBequivCpmod2
- A,B,C,T は整数
入力
入力は以下の形式で標準入力から与えられる。
A B C T
出力
時刻 T に初めて 3 人が同じ地点にいる状態になる確率を textmod998244353 で計算して、答えを出力せよ。
入力例 1
出力例 1
時刻 1 に初めて 3 人が同じ地点にいる状態になる確率は frac18 です。873463809times8equiv1pmod998244353 なので 873463809 を出力します。
入力例 2
出力例 2
時刻 0 の時点ですでに 3 人が同じ地点にいる場合もあります。
入力例 3
出力例 3
入力例 4
出力例 4