题目描述

整数 $N,M,V,A$ が与えられます． 次のような操作を考えます．

• $1$ 以上 $V$ 以下の整数からなる長さ $N$ の整数列 $x=(x_1,x_2,\cdots,x_N)$ を選ぶ．
• $1$ 以上 $V$ 以下の整数からなる長さ $M$ の整数列 $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$ で割った余りを求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

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

输出格式

答えを出力せよ．

题目大意

给定正整数 $N,M,V,A$，对于所有值域为 $[1,V]$ 的正整数数列 $\{x_N\},\{y_M\}$，求下列问题的答案之和：

• 定义一个变量 $a$，初值为 $A$。
• 从小到大枚举非负整数 $i \in [0, N \times M-1]$，将 $a$ 替换成 $a,x_{(i \bmod N)+1},y_{(i \bmod M)+1}$ 的中位数。
• 问题的答案为 $a$ 最终的值。

对 $998244353$ 取模。

2 1 2 1

11

2 2 5 4

2019

2100 2300 2201 2022

407723438

提示

制約

• $1\ \leq\ N,M\ \leq\ 200000$
• $1\ \leq\ A\ \leq\ V\ \leq\ 200000$
• 入力される値はすべて整数である

Sample Explanation 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$ です．