Problem Background

Xiao Q is a deity, especially fond of polynomials.

One day, Xiao K asked a question:

Given sequences \( g \) and \( h \) of length \( n \), find \( f \) such that \( f_n = \sum_{k=0}^{n} g_k h_{n-k} \).

Xiao Q told Xiao K: You're such a newbie, this is just a simple convolution, how did you learn FFT?

Then Xiao K spent a month studying FFT and NTT. He went back to ask Xiao Q another question:

Given sequences \( g \) and \( h \) of length \( n \), find \( f \) such that \( f_n = \sum_{k=0}^{n} \binom{n}{k} g_k h_{n-k} \).

Xiao Q told Xiao K: You're such a newbie, this is just a simple convolution, how did you learn FFT?

Then Xiao K spent another month studying FFT and NTT. He went back to ask Xiao Q another question:

Given sequences \( g \) and \( h \) of length \( n \), find \( f \) such that \( f_n = \sum_{k=0}^{n} k^n g_k h_{n-k} \).

Xiao Q told Xiao K: You're such a newbie, this is just a simple convolution, how did you learn FFT?

Then he looked closely and was stumped, realizing he couldn't solve this problem.

To outsmart Xiao K, you need to tell him the solutions for four special cases.

Problem Description

Given specific sequences \( g \) and \( h \), find \( f_n \) such that \( f_n = \sum_{k=0}^{n} k^n g_k h_{n-k} \).

This problem has five subtasks, the first four of which specify different forms of \( g \) and \( h \), requiring the calculation of \( f_n \). The fifth subtask does not depend on this equation but is similar in form.

Note, all outputs should be modulo \( 998244353 \) (\( 119 \times 2^{23} + 1 \), a prime number).

Subtask 1 (4 pts):

Given an \( n \), you need to answer \( q \) queries, each query specifying 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 specify the same form of sequences \( g \) and \( h \), but with different data ranges, so read the data ranges carefully.

You need to answer \( q \) queries, each query specifying two integers \( n \) and \( 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 specifying two integers \( n \) and \( 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 specifying two integers \( n \) and \( m \).

Note the meanings of \( n \) and \( m \) below, do not mix them up.

\[ \sum_{k=0}^{m} (k+1)^m \frac{(k+1)^{n+1}}{(k+1)!} \sum_{i=0}^{m-k} \frac{\binom{2n+1}{i} (-1)^{m-k}}{(m-k-i)! (k+1)^i} \]

You need to output the value of the above expression.

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

Input Format

The first line contains an integer \( op \), indicating the subtask number.

If \( op = 1 \):

The second line contains an integer \( n \), the third line contains an integer \( q \);

Next, \( q \) lines follow, each containing an integer \( m \).

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

The second line contains an integer \( q \);

Next, \( q \) lines follow, each containing two integers \( n \) and \( m \).

All variable meanings are as described in the problem statement.

Output Format

For each query, output one line containing an integer, which is the answer.

Sample Input and Output

Sample Input #1

1
5
2
2
3

Sample Output #1

1
33

Sample Input #2

2
2
4 2
18 7

Sample Output #2

440891256
841247136

Sample Input #3

4
2
4 2
20 9

Sample Output #3

65
429844531

Sample Input #4

5
2
4 2
30 12

Sample Output #4

58
475486366

Notes

Sample Explanation 1

In this sample, the first subtask is to be solved, with \( n = 5 \) and \( q = 2 \).

For the first query, \( m = 2 \), then (omitting the zero terms):

\[ [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_1 h_4 = 1 \]

For 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_1 h_4 + 2^5 \times g_2 h_3 = 33 \]

Sample Explanation 2

In this sample, the second subtask is to be solved, with \( q = 2 \).

For the first query, \( n = 4 \) and \( m = 2 \), then:

\[ [g_0 \ g_1 \ g_2 \ g_3 \ g_4] = \left[ \frac{1}{6} \ \ \frac{1}{24} \ \ \frac{1}{120} \ \ \frac{1}{720} \ \ \frac{1}{5040} \right] \]

\[ [h_0 \ h_1 \ h_2 \ h_3 \ h_4] = [0 \ 0 \ 1 \ -1 \ \frac{1}{2}] \]

\[ f_5 = 1^4 \times g_1 h_3 + 2^4 \times g_2 h_2 = \frac{11}{120} \]

\( f_5 = \frac{11}{120} \) modulo \( 998244353 \) equals \( 440891256 \).

The second query is too large for sample explanation.

Sample Explanation 3

In this sample, the fourth subtask is to be solved, with \( q = 2 \).

For the first query, \( n = 4 \) and \( m = 2 \), then:

\[ [g_0 \ g_1 \ g_2 \ g_3 \ g_4] = [0 \ 1 \ 2 \ \frac{3}{2} \ \frac{2}{3}] \]

\[ [h_0 \ h_1 \ h_2 \ h_3 \ h_4] = [1 \ -1 \ \frac{1}{2} \ -\frac{1}{6} \ \frac{1}{24}] \]

\[ f_5 = 1^4 \times g_1 h_3 + 2^4 \times g_2 h_2 + 3^4 \times g_3 h_1 + 4^4 \times g_4 h_0 = 65 \]

The second query is too large for sample explanation.

Sample Explanation 4

In this sample, the fifth subtask is to be solved, with \( q = 2 \).

For the first query, \( n = 4 \) and \( m = 2 \), then enumerating \( k \) and \( i \):

\[ k = 0, i = 0: (k+1)^m \frac{(k+1)^{n+1}}{(k+1)!} \frac{\binom{2n+1}{i} (-1)^{m-k}}{(m-k-i)! (k+1)^i} = \frac{1}{2} \]

\[ k = 0, i = 1: (k+1)^m \frac{(k+1)^{n+1}}{(k+1)!} \frac{\binom{2n+1}{i} (-1)^{m-k}}{(m-k-i)! (k+1)^i} = 9 \]

\[ k = 0, i = 2: (k+1)^m \frac{(k+1)^{n+1}}{(k+1)!} \frac{\binom{2n+1}{i} (-1)^{m-k}}{(m-k-i)! (k+1)^i} = 36 \]

\[ k = 1, i = 0: (k+1)^m \frac{(k+1)^{n+1}}{(k+1)!} \frac{\binom{2n+1}{i} (-1)^{m-k}}{(m-k-i)! (k+1)^i} = -64 \]

\[ k = 1, i = 1: (k+1)^m \frac{(k+1)^{n+1}}{(k+1)!} \frac{\binom{2n+1}{i} (-1)^{m-k}}{(m-k-i)! (k+1)^i} = -288 \]

\[ k = 2, i = 0: (k+1)^m \frac{(k+1)^{n+1}}{(k+1)!} \frac{\binom{2n+1}{i} (-1)^{m-k}}{(m-k-i)! (k+1)^i} = \frac{729}{2} \]

Summing all, the result is \( 58 \).

The second query is too large for sample explanation.

Data Range

This problem uses batched testing, with different subtask requirements.

All inputs are positive integers.

见题面 Input 部分

见题面 Output 部分