题目描述

数直線上に人 $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$ で計算して、答えを出力せよ。

题目大意

一个数轴上有 $3$ 个人，分别在点 $A,B,C$ 上，且 $A,B,C$ 奇偶性相同。这 $3$ 个人从时刻 $0$ 开始移动，每经过一个时刻，一个人就会从原先所在的位置 $x$ 走到位置 $x+1$ 或 $x-1$，问在 $T$ 时刻有多大的概率 $3$ 个人 第一次 走到相同的位置，答案对 $998244353$ 取模，$0\le A,B,C,T\le 10^5$。

1 1 3 1

873463809

0 0 0 0

1

0 2 8 9

744570476

47717 21993 74147 76720

844927176

提示

制約

• $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$ 人が同じ地点にいる場合もあります。