Modular Convolution Sum

Given two sequences g and h defined in different ways for various subtasks, you are to compute f_n defined by

$$ f_n = \sum_{k=0}^{n} k^n\, g_k\, h_{n-k} $$

All outputs should be given modulo $$998244353$$ (i.e. $$119\times2^{23}+1$$, which is prime).

The problem consists of 5 subtasks:

• Subtask 1 (4 pts): You are given a fixed integer n and q queries. For each query an integer m is given. For all indices $$0\le k\le n$$, the sequences are defined as $$ g_k = \begin{cases}1,& k<m\\0,& k\ge m \end{cases}, \quad h_k = 1. $$ Thus, you must compute $$ f_n = \sum_{k=0}^{n} k^n\, g_k = \sum_{k=0}^{\min(n, m-1)} k^n. $$
• Subtasks 2 & 3 (16 pts each): Each query provides two integers n and m. The sequences are defined by $$ g_k = \frac{1}{(k+m+1)!}, \quad h_k = \begin{cases}0, & k<m\\ \frac{(-1)^{k-m}}{(k-m)!}, & k\ge m \end{cases}, \quad 0\le k\le n. $$ Compute the corresponding f_n.
• Subtask 4 (32 pts): Each query gives two integers n and m with sequences defined by $$ g_k = \frac{k^m}{k!}, \quad h_k = \frac{(-1)^k}{k!}, \quad 0\le k\le n. $$ Compute $$ f_n = \sum_{k=0}^{n} k^n\, \frac{k^m}{k!}\, \frac{(-1)^{n-k}}{(n-k)!}. $$
• Subtask 5 (32 pts): Each query provides two integers n and m (note that the roles of n and m are exactly as given and should not be interchanged). You need to compute the value of $$ \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}. $$ This subtask is similar in flavor to the previous ones because the sums initially involve exponential expressions.

Note: In all subtasks, all calculations (including factorials and powers) must be performed modulo $$998244353$$.

inputFormat

The input begins with an integer t representing the subtask type (an integer from 1 to 5).

If t = 1, the next line contains two integers n and q, followed by q lines each containing an integer m.

If t = 2, t = 3, t = 4 or t = 5, the next line contains an integer q, followed by q lines, each containing two integers n and m.

outputFormat

For each query, output a single line containing the computed value of f_n (or the corresponding sum in subtask 5), modulo $$998244353$$.

sample

1
5 2
3
6

3125
15625