分数: 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