分数: 800 点
问题陈述
给定的是整数 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 中位数为 a,x_{(i \bmod N)+1},y_{(i \bmod M)+1}.
- 打印最终值 a.
考虑对每对可能的序列执行此过程 x,y。求将要打印的值的总和,模数 998244353.
约束
- 1 \leq N,M \leq 200000
- 1 \leq A \leq V \leq 200000
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M V A
输出
打印答案。
样本输入 1
2 1 2 1
示例输出 1
11
例如,当 x=(1,2),y=(2),程序如下。
- 初始化 a 与 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))。在其他五起案件中, 将打印 1 。 因此,答案是 2 \times 3 + 1\times 5=11.
示例输入 2
2 2 5 4
示例输出 2
2019
示例输入 3
2100 2300 2201 2022
示例输出 3
407723438