Background

As everyone knows, Cai Xukun, who “debuted” from the national talent show and has been in kindergarten for two and a half years, likes singing, dancing, rap, and basketball. As Irving’s teacher, his basketball skills are naturally much better than those of the “ikun” fans.

Problem Description

On Cai Xukun’s exclusive basketball court in the “national talent show kindergarten”, there are a total of $N$ exclusive basketballs, among which $M$ are deflated. Due to Cai Xukun’s superb skills, when he shoots a deflated ball, it must go in, and when he shoots an inflated ball, it must not go in.

Cai Xukun holds $S$ touring basketball performances. In the $i$-th performance, the ikun fans specify the number of shots $k_i$. They will prepare $n_i$ balls from the $N$ exclusive basketballs and place them on the court, among which exactly $m_i$ are deflated. Cai Xukun will randomly choose $k_i$ balls from these $n_i$ exclusive basketballs to shoot. If he makes $x$ shots, then the failure score of this performance is $x^L$. The ikun fans want to know, for these $S$ performances, the result of the expected failure score modulo $998244353$. The basketball performances are independent of each other.

Input Format

The first line contains four positive integers $N, M, S, L$, representing the total number of Cai Xukun’s exclusive basketballs, the total number of deflated basketballs, the number of touring basketball performances, and the failure score parameter.

Each of the next $S$ lines contains three positive integers $n_i, m_i, k_i$, representing, for the $i$-th performance, the number of exclusive basketballs used, the number of deflated basketballs among them, and the number of shots specified by the ikun fans.

Output Format

Output $S$ lines in total. The $i$-th line contains a positive integer, representing the expected failure score of the $i$-th performance modulo $998244353$.

3 2 1 3
3 2 2

332748121

Hint

For the sample, we explain as follows. Let the failure score be $X$. Cai Xukun has probability $\frac{1}{3}$ to make $2$ shots, and probability $\frac{2}{3}$ to make $1$ shot. The expected failure score is $E(x)=\frac{2^3}{3}+\frac{1^3*2}{3}=\frac{10}{3}$, and $\frac{10}{3}\equiv 332748121\pmod{998244353}$.

Subtask 1 ($15\%$): $1\leq L\leq2$.

Subtask 2 ($10\%$): $1\leq N\leq10^5$.

Subtask 3 ($75\%$): No special constraints.

For all testdata, $1\leq S\leq200$, $1\leq L\leq2\times 10^5$, $1\leq M\leq N\leq2\times 10^7$. Also, for $1\leq i\leq S$, we have $1\leq m_i,k_i\leq n_i\leq N$, $1\leq m_i\leq M$.

Translated by ChatGPT 5