某不科学的单调序列的首项加权和¶

背景故事¶

小A在做学园都市第零次高中模拟考试试卷时，发现了一道有意思的数学题，于是他决定结合算法知识进行数据范围加强。

给定整数 \(n,m,k,c\) .对每个满足 \(1\le x_1\le x_2\le\cdots\le x_n\le m\) 的整数序列，计入权值 \(kx_1+c\) .求所有序列的权值之和，对 \(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 \]

当 \(n=1\) 时仅有一层求和；当 \(m=0\) 时没有合法序列，答案为零。

一行四个整数 \(n,m,k,c\) ，依次表示长度、编号上界、首项系数与常数项。

一行一个整数，表示答案在 \([0,p-1]\) 中的余数。

2 3 2 1

六个序列的权值依次为 \(3,3,3,5,5,7\) ，总和为 \(26\) .

六个合法序列及其权值。

1 0 9 4

没有合法序列。

1 998244353 0 1

共有 \(998244353\) 个长度为一的序列，每个权值为一。

\(1\le n\le10^7\) ；\(0\le m,k,c\le10^9\) .所有输入均为整数。