三人组

题目描述

数轴上有 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$(所有移动的选择都是随机且独立的)。

求「在时间 $T$,三个人第一次到达同一点」的概率,对 $998244353$ 取模。

对 $998244353$ 取模的有理数是什么?

可以证明,所求概率总是有理数。 此外,在本问题的约束下,当该值用两个互质的整数 $P$ 和 $Q$ 表示为 $\frac{P}{Q}$ 时,可以证明存在唯一的整数 $R$,使得 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \le R \lt 998244353$。求这样的 $R$。

输入格式

输入按以下格式从标准输入给出。

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

输出格式

输出「在时间 $T$,三个人第一次到达同一点」的概率对 $998244353$ 取模的值。

样例

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

数据范围

• $0 \le A, B, C, T \le 10^5$
• $A \equiv B \equiv C \pmod{2}$
• $A$、$B$、$C$、$T$ 均为整数。