/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 800 点
問題文
整数 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 で割った余りを求めてください．
制約
- 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=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 です．
入力例 2
2 2 5 4
出力例 2
2019
入力例 3
2100 2300 2201 2022
出力例 3
407723438
Score : 800 points
Problem Statement
Given are integers N, M, V, and A. Consider the following procedure.
- Choose a sequence of N integers between 1 and V (inclusive): x=(x_1,x_2,\cdots,x_N).
- Choose a sequence of M integers between 1 and V (inclusive): y=(y_1,y_2,\cdots,y_M).
- Let a be a variable and initialize it with a=A.
- For each i=0,1,\cdots,N \times M-1, do the following.
- Replace the value of a with the median of a,x_{(i \bmod N)+1},y_{(i \bmod M)+1}.
- Print the final value of a.
Consider doing this procedure with every possible pair of sequences x,y. Find the sum of the values that will be printed, modulo 998244353.
Constraints
- 1 \leq N,M \leq 200000
- 1 \leq A \leq V \leq 200000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M V A
Output
Print the answer.
Sample Input 1
2 1 2 1
Sample Output 1
11
For example, when x=(1,2),y=(2), the procedure goes as follows.
- Initialize a with a=1.
- For i=1: replace the value of a with the median of a(=1),x_1(=1),y_1(=2), which is 1.
- For i=2: replace the value of a with the median of a(=1),x_2(=2),y_1(=2), which is 2.
- Print a(=2).
There are three cases where 2 will be printed: (x=(1,2),y=(2)), (x=(2,1),y=(2)), (x=(2,2),y=(2)). In the other five cases, 1 will be printed. Therefore, the answer is 2 \times 3 + 1\times 5=11.
Sample Input 2
2 2 5 4
Sample Output 2
2019
Sample Input 3
2100 2300 2201 2022
Sample Output 3
407723438