Description

Given a polynomial $F(x)=\displaystyle \sum_{i=0}^{n-1}f_ix^i$ of degree less than $n$, and $m$ pairs $(a_i,k_i)$, satisfying $\displaystyle \sum_{i=1}^m k_i=n$.

For each pair $(a_i,k_i)$, find $F^{(j)}(a_i)$, $\forall\, 0\le j< k_i$, with the answers taken modulo $998244353$.

Here $F^{(i)}(x)$ denotes the $i$-th derivative of $F(x)$.

Input Format

The first line contains two positive integers $n,m$.

The second line contains $n$ integers, namely $f_0,f_1,\cdots ,f_{n-1}$ in order.

Each of the next $m$ lines represents the values of $a_i,k_i$ on the $i$-th line.

Output Format

Output $m$ lines.

The $i$-th line contains $k_i$ numbers, representing $F(a_i),F'(a_i),F^{(2)}(a_i),\cdots ,F^{(k_i-1)}(a_i)$ in order.

All answers are taken modulo $998244353$.

11 11
18 2 6 17 7 19 17 6 2 12 14
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1

120
23750
1107240
18147258
161737928
973451550
464732548
722342802
682083299
545845982
686473504

11 4
18 2 6 17 7 19 17 6 2 12 14
4 2
15 3
5 2
20 4

18147258 44343650 
804760733 115057816 300031140 
161737928 317914212 
73381527 279355195 666843568 217219267

Hint

For all testdata, $1\le m\le n\le 64000$, $0\le f_i,a_i<998244353$.

It is guaranteed that each $k_i$ is a positive integer and $\displaystyle \sum_{i=1}^mk_i =n$.

It is guaranteed that the $a_i$ are pairwise distinct.

Translated by ChatGPT 5