题目描述

给定整数 $N, M, V, A$。考虑如下操作：

• 选择一个长度为 $N$，每个元素都是 $1$ 到 $V$ 之间整数的整数列 $x=(x_1,x_2,\cdots,x_N)$。
• 选择一个长度为 $M$，每个元素都是 $1$ 到 $V$ 之间整数的整数列 $y=(y_1,y_2,\cdots,y_M)$。
• 准备一个变量 $a$，初始时 $a=A$。
• 对于 $i=0,1,\cdots,N\times M-1$，执行以下操作：
  • 用 $a, x_{(i\bmod N)+1}, y_{(i\bmod M)+1}$ 的中位数替换 $a$ 的值。
• 输出最终的 $a$ 的值。

请你求出，枚举所有可能的整数列 $x, y$，通过上述操作输出的 $a$ 的值的总和对 $998244353$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$ $V$ $A$

输出格式

输出答案。

样例 1

输入

2 1 2 1

输出

11

样例 2

输入

2 2 5 4

输出

2019

样例 3

输入

2100 2300 2201 2022

输出

407723438

说明/提示

限制条件

• $1\leq N, M \leq 200000$
• $1\leq A \leq V \leq 200000$
• 输入的所有值均为整数

样例解释 1

例如，当 $x=(1,2), y=(2)$ 时，操作过程如下：

• $a=1$ 初始化。
• $i=1$：$a$ 的值变为 $a(=1), x_1(=1), y_1(=2)$ 的中位数，即 $1$。
• $i=2$：$a$ 的值变为 $a(=1), x_2(=2), y_1(=2)$ 的中位数，即 $2$。
• 输出 $a(=2)$。

最终输出 $2$ 的情况有 $(x=(1,2),y=(2))$，$(x=(2,1),y=(2))$，$(x=(2,2),y=(2))$ 共 $3$ 种，其余 $5$ 种情况输出均为 $1$。因此答案为 $2\times 3 + 1\times 5 = 11$。

由 ChatGPT 4.1 翻译