当前没有测试数据。

Ex - Trio

得分：600分

问题描述

在一条数轴上，有人员1、人员2和人员3。在时间0，人员1在点A，人员2在点B，人员3在点C。
这里，A、B和C都是整数，且A ≡ B ≡ C (mod 2)。

在时间0，这三个人开始随机游走。具体来说，在时间t（t是非负整数）时，处于点x的人员在时间t+1时会以相等的概率移动到点(x-1)或点(x+1)。 (所有移动的选择都是随机和独立的。)

找到概率（模$998244353$），在时间T时这三个人第一次同时到达相同的点。

约束

• $0 \leq A, B, C, T \leq 10^5$
• $A \equiv B \equiv C \pmod{2}$
• $A, B, C$和$T$是整数。

输入

输入从标准输入中以以下格式给出：

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

输出

找到概率（模$998244353$），在时间T时这三个人第一次同时到达相同的点，并打印答案。

1 1 3 1

873463809

这三个人在时间1第一次同时到达相同的点，概率为$\frac{1}{8}$。由于$873463809 \times 8 \equiv 1 \pmod{998244353}$，应该输出$873463809$。

0 0 0 0

1

这三个人可能在时间0已经在同一个点上。

0 2 8 9

744570476

47717 21993 74147 76720

844927176