题目描述

在数轴上有三个人 $1$、$2$、$3$。在时刻 $0$，人 $1$ 在位置 $A$，人 $2$ 在位置 $B$，人 $3$ 在位置 $C$。
其中 $A$、$B$、$C$ 都是整数，并且满足 $A \equiv B \equiv C \pmod{2}$。

三个人从时刻 $0$ 开始进行随机游走。具体来说，时刻 $t$（$t$ 为非负整数）时，在位置 $x$ 的人，会以相等的概率在时刻 $t+1$ 移动到位置 $x-1$ 或 $x+1$。（所有人的移动方向选择都是随机且独立的。）

请计算，从时刻 $0$ 开始，三个人第一次在同一位置相遇的时刻为 $T$ 的概率，并对 $998244353$ 取模。

关于有理数 $\bmod\ 998244353$：可以证明，所求概率一定是有理数。在本题的约束下，若用互质的两个整数 $P$、$Q$ 表示为 $\frac{P}{Q}$，则一定存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出这个 $R$。

输入格式

输入为一行，包含四个整数：

$A$ $B$ $C$ $T$

输出格式

输出三个人第一次在时刻 $T$ 相遇的概率，对 $998244353$ 取模后的结果。

样例 1

输入

1 1 3 1

输出

873463809

样例 2

输入

0 0 0 0

输出

1

样例 3

输入

0 2 8 9

输出

744570476

样例 4

输入

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$ 均为整数

样例解释 1

三个人第一次在时刻 $1$ 相遇的概率为 $\frac{1}{8}$。$873463809 \times 8 \equiv 1 \pmod{998244353}$，所以输出 $873463809$。

样例解释 2

在时刻 $0$，三个人也可能已经在同一位置。

由 ChatGPT 4.1 翻译