问题描述

在数轴上有三个人：人1，人2和人3。在时间0时刻，人1位于点A，人2位于点B，人3位于点C。 这里，A、B和C都是整数，而且满足A ≡ B ≡ C (mod 2)。

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

找到概率（模$998244353$），即在时间T时刻，三个人首次位于同一点。

用模$998244353$表示有理数是什么？我们可以证明所求概率始终是一个有理数。此外，在该问题的约束条件下，当将该值表示为由两个互素的整数P和Q构成的$\\frac{P}{Q}$时，我们可以证明存在唯一的整数R，使得$R \\times Q \\equiv P\\pmod{998244353}$且$0 \\leq R \\lt 998244353$。找到这样的R。

约束条件

• $0 \leq A, B, C, T \leq 10^5$
• $A ≡ B ≡ C (mod 2)$
• A、B、C和T是整数。

输入

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

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

输出

找到概率（模$998244353$），即在时间T时刻，三个人首次位于同一点，并输出答案。

示例输入1

1 1 3 1

示例输出1

873463809

三个人在时间1时刻首次位于同一点的概率为$\frac{1}{8}$。由于$873463809 \times 8 \equiv 1 \pmod{998244353}$，因此应该输出$873463809$。

示例输入2

0 0 0 0

示例输出2

1

三个人可能在时间0时刻就已经位于同一点。

示例输入3

0 2 8 9

示例输出3

744570476

示例输入4

47717 21993 74147 76720

示例输出4

844927176