E - Cyclic Medians 解説 /

実行時間制限: 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