AT_abc289_h [ABC289Ex] Trio

[problemUrl]: https://atcoder.jp/contests/abc289/tasks/abc289_h 数直線上に人 $ 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 $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ A $ $ B $ $ C $ $ T $

時刻 $ 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 $ は整数 ### Sample Explanation 1 時刻 $ 1 $ に初めて $ 3 $ 人が同じ地点にいる状態になる確率は $ \frac{1}{8} $ です。$ 873463809\ \times\ 8\ \equiv\ 1\ \pmod{998244353} $ なので $ 873463809 $ を出力します。 ### Sample Explanation 2 時刻 $ 0 $ の時点ですでに $ 3 $ 人が同じ地点にいる場合もあります。