Background

Little Q is a genius and especially likes polynomials.

One day, Little K asked a question:

Given two sequences $g, h$ of length $n$, find $f$ such that $f_n=\sum\limits_{k=0}^{n}g_kh_{n-k}$.

Little Q said to Little K: You are such a newbie. Isn’t this just an easy convolution? What did you learn FFT for?

Then Little K spent a month learning FFT and NTT, and went to ask Little Q another question:

Given two sequences $g, h$ of length $n$, find $f$ such that $f_n=\sum\limits_{k=0}^{n}\binom{n}{k}g_kh_{n-k}$.

Little Q said to Little K: You are such a newbie. Isn’t this just an easy convolution? What did you learn FFT for?

Then Little K spent another month learning FFT and NTT, and went to ask Little Q yet another question:

Given two sequences $g, h$ of length $n$, find $f$ such that $f_n=\sum\limits_{k=0}^{n}k^ng_kh_{n-k}$.

Little Q said to Little K: You are such a newbie. Isn’t this just an easy convolution? What did you learn FFT for?

Then he took a careful look and was stunned, realizing he could not solve this problem.

To totally defeat Little K, you need to tell him how to handle $4$ special cases.

Background

Little Q is a genius and especially likes polynomials.

One day, Little K asked a question:

Given two sequences $g, h$ of length $n$, find $f$ such that $f_n=\sum\limits_{k=0}^{n}g_kh_{n-k}$.

Little Q said to Little K: You are such a newbie. Isn’t this just an easy convolution? What did you learn FFT for?

Then Little K spent a month learning FFT and NTT, and went to ask Little Q another question:

Given two sequences $g, h$ of length $n$, find $f$ such that $f_n=\sum\limits_{k=0}^{n}\binom{n}{k}g_kh_{n-k}$.

Little Q said to Little K: You are such a newbie. Isn’t this just an easy convolution? What did you learn FFT for?

Then Little K spent another month learning FFT and NTT, and went to ask Little Q yet another question:

Given two sequences $g, h$ of length $n$, find $f$ such that $f_n=\sum\limits_{k=0}^{n}k^ng_kh_{n-k}$.

Little Q said to Little K: You are such a newbie. Isn’t this just an easy convolution? What did you learn FFT for?

Then he took a careful look and was stunned, realizing he could not solve this problem.

To totally defeat Little K, you need to tell him how to handle $4$ special cases.

Problem Description

Given specific sequences $g, h$, compute $f_n$ satisfying $f_n=\sum\limits_{k=0}^{n}k^ng_kh_{n-k}$.

This problem has five subtasks. The first four subtasks give different forms of $g, h$ and ask you to compute $f_n$. The fifth subtask does not depend on this equation, but it looks similar in form.

Note: all outputs in this problem should be taken modulo $998244353$ ($119\times 2^{23}+1$, a prime).

---

Subtask 1 (4 pts):

Given an integer $n$, you need to answer $q$ queries. Each query gives an integer $m$.

For each query, $g$ and $h$ are as follows ($0\leq k\leq n$):

$$g_k=\begin{cases}1,&k<m\\0,&k\geq m\end{cases}$$ $$h_k=1$$

You need to output the value of $f_n$.

---

Subtask 2, 3 (16, 16 pts):

These two subtasks use the same form of sequences $g, h$, but have different constraints. Please read the constraints carefully.

You need to answer $q$ queries. Each query gives two integers $n, m$.

For each query, $g$ and $h$ are as follows ($0\leq k\leq n$):

$$g_k=\frac{1}{(k+m+1)!}$$ $$h_k=\begin{cases}0,&k<m\\\frac{(-1)^{k-m}}{(k-m)!},&k\geq m\end{cases}$$

You need to output the value of $f_n$.

---

Subtask 4 (32 pts):

You need to answer $q$ queries. Each query gives two integers $n, m$.

For each query, $g$ and $h$ are as follows ($0\leq k\leq n$):

$$g_k=\frac{k^m}{k!}$$ $$h_k=\frac{(-1)^k}{k!}$$

You need to output the value of $f_n$.

---

Subtask 5 (32 pts):

You need to answer $q$ queries. Each query gives two integers $n, m$.

Note the meaning of $n, m$ below. Do not swap them.

$$\sum\limits_{k=0}^{m}(k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\sum\limits_{i=0}^{m-k}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}$$

You need to output the value of the expression above.

Similar to the first four subtasks, the summation starts with a power term.

Input Format

The first line contains an integer $op$, indicating the subtask number.

If $op=1$:

The second line contains an integer $n$, and the third line contains an integer $q$.

Then follow $q$ lines, each containing an integer $m$.

If $op\in \{2,3,4,5\}$:

The second line contains an integer $q$.

Then follow $q$ lines, each containing two integers $n, m$.

The meaning of all variables is given in the problem description.

Output Format

For each query, output one integer per line, indicating the answer.

1
5
2
2
3

1
33

2
2
4 2
18 7

440891256
841247136

4
2
4 2
20 9

65
429844531

5
2
4 2
30 12

58
475486366

Hint

Sample Explanation 1

In this sample, you need to solve Subtask 1, with $n=5,\ \ q=2$.

In the first query, $m=2$, then (omitting terms whose addend is $0$):

$$[g_0\ \ g_1\ \ g_2\ \ g_3\ \ g_4\ \ g_5]=[1\ \ 1\ \ 0\ \ 0\ \ 0\ \ 0]$$$$[h_0\ \ h_1\ \ h_2\ \ h_3\ \ h_4\ \ h_5]=[1\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1]$$$$f_5=1^5\times g_1h_4=1$$

In the second query, $m=3$, then:

$$[g_0\ \ g_1\ \ g_2\ \ g_3\ \ g_4\ \ g_5]=[1\ \ 1\ \ 1\ \ 0\ \ 0\ \ 0]$$$$[h_0\ \ h_1\ \ h_2\ \ h_3\ \ h_4\ \ h_5]=[1\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1]$$$$f_5=1^5\times g_1h_4+2^5\times g_2h_3=33$$

---

Sample Explanation 2

In this sample, you need to solve Subtask 2, with $q=2$.

In the first query, $n=4,\ \ m=2$, then:

$$[g_0\ \ g_1\ \ g_2\ \ g_3\ \ g_4]=[\dfrac{1}{6}\ \ \dfrac{1}{24}\ \ \dfrac{1}{120}\ \ \dfrac{1}{720}\ \ \dfrac{1}{5040}]$$$$[h_0\ \ h_1\ \ h_2\ \ h_3\ \ h_4]=[0\ \ 0\ \ 1\ \ -1\ \ \dfrac{1}{2}]$$$$f_4=1^4\times g_1h_3+2^4\times g_2h_2=\dfrac{11}{120}$$

After taking modulo $998244353$, $f_4=\dfrac{11}{120}$ equals $440891256$.

The second query has constraints that are too large, so no sample explanation is provided.

---

Sample Explanation 3

In this sample, you need to solve Subtask 4, with $q=2$.

In the first query, $n=4,\ \ m=2$, then:

$$[g_0\ \ g_1\ \ g_2\ \ g_3\ \ g_4]=[0\ \ \ 1\ \ \ 2\ \ \ \dfrac{3}{2}\ \ \dfrac{2}{3}]$$$$[h_0\ \ h_1\ \ h_2\ \ h_3\ \ h_4]=[1\ \ -1\ \ \dfrac{1}{2}\ \ -\dfrac{1}{6}\ \ \dfrac{1}{24}]$$$$f_4=1^4\times g_1h_3+2^4\times g_2h_2+3^4\times g_3h_1+4^4\times g_4h_0=65$$

The second query has constraints that are too large, so no sample explanation is provided.

---

Sample Explanation 4

In this sample, you need to solve Subtask 5, with $q=2$.

In the first query, $n=4,\ \ m=2$, enumerate $k, i$:

$$k=0,\ \ i=0:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=\dfrac{1}{2}$$$$k=0,\ \ i=1:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=9$$$$k=0,\ \ i=2:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=36$$$$k=1,\ \ i=0:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=-64$$$$k=1\ \ i=1:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=-288$$$$k=2\ \ i=0:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=\dfrac{729}{2}$$

Adding them all up gives $58$.

The second query has constraints that are too large, so no sample explanation is provided.

---

Constraints

This problem uses bundled testdata, and different subtasks have different statements.

Subtask ID	$q\leq$	$n\leq$	$m\leq$	Points
1	$5\times 10^5$	$10^5$	$\min(10^5,n)$	4
2		$2\times 10^5$	$20$	16
3	$20$	$998244352$
4 (31-40)	$5\times 10^5$	$2\times 10^5$	$10$	32
4 (51-60)	$20$	$10^{10^5}$
5	$5\times 10^5$	$2\times 10^3$

All inputs are positive integers.

Translated by ChatGPT 5