A Certain Unscientific Weighted Sum of First Values of Monotone Sequences¶

Reference time limit: 0.5 seconds (environment R30; estimate only).
Actual time limit: twice the standard program’s baseline time on the slowest official test file in the target environment, rounded up to a multiple of 0.5 seconds.
Memory limit: 128 MB

Story¶

While working through the paper for Academy City's Zeroth High School Mock Exam, Xiao A came across an interesting mathematics problem and decided to use his knowledge of algorithms to expand its input bounds.

Formal Problem Statement¶

Given integers \(n,m,k,c\) , assign weight \(kx_1+c\) to each integer sequence satisfying \(1\le x_1\le x_2\le\cdots\le x_n\le m\) . Find the sum of these weights modulo \(p=998244353\) .

\[ \sum_{x_n=1}^{m}\sum_{x_{n-1}=1}^{x_n}\cdots\sum_{x_1=1}^{x_2}(kx_1+c)\pmod p \]

For \(n=1\) there is one sum. For \(m=0\) there are no valid sequences and the answer is zero.

Input Format¶

One line contains \(n,m,k,c\) : the length, largest section number, first-value coefficient, and constant term.

Output Format¶

Print one integer, the remainder in \([0,p-1]\) .

Sample 1¶

Input¶

2 3 2 1

Output¶

Explanation¶

The six sequences have weights \(3,3,3,5,5,7\) , totalling \(26\) .

The six valid sequences and their weights.

Sample 2¶

Input¶

1 0 9 4

Output¶

Explanation¶

There are no valid sequences.

Sample 3¶

Input¶

1 998244353 0 1

Output¶

Explanation¶

There are \(998244353\) one-element sequences, each of weight one.

Constraints and Guarantees¶

\(1\le n\le10^7\) ; \(0\le m,k,c\le10^9\) . All inputs are integers.

Test Groups¶

Score	Additional restriction
20%	\(n,m\le12\)
30%	\(m\le2000\)
50%	No additional restriction

Reference environment and measurements