← 返回题目列表

AtCoder · abc289_h

Ex. 三重奏

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

在数轴上是人 1, 人 2和人 3。 时 0, 人 1 已到 A, 人 2 已到 B和人 3 已到 C.
在这里, A, B,和 C 都是整数,并且 A \equiv B \equiv C \pmod{2}.

时间 0,三人开始随机游走。 具体来说,一个人在某个时刻 x 时间 t (t 是一个非负整数)移动到点 (x-1) 或点 (x+1) 时间 (t+1) 具有相同的概率。 (所有的动作选择都是随机且独立的。)

求概率,模 998244353,现在是 T 三个人第一次处于同一点。

什么是有理数模 998244353? 我们可以证明所求的概率始终是有理数。 而且,在这个问题的约束下,当值表示为 \frac{P}{Q} 由两个互质整数 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 \equiv B \equiv C \pmod{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