形式幂级数快速幂（稀疏）

【题目描述】

给定一个形式幂级数 $f(x) = \sum_{i=0}^{N-1} a_i x^i \in \mathbb{F}_{998244353}[[x]]$ 和一个非负整数 $M$。 $f$ 中只有 $K$ 个系数非零，输入中只给出这些系数 $a_{i_k}$。

计算 $(f(x))^M = \sum_{i=0}^{\infty} b_i x^i$ 的前 $N$ 项。

【输入】

$N$ $K$ $M$
$i_0$ $a_{i_0}$
$\vdots$
$i_{K-1}$ $a_{i_{K-1}}$

【输出】

$b_0$ $b_1$ $\cdots$ $b_{N - 1}$

【输入样例】

5 2 3
0 1
2 1

【输出样例】

1 0 3 0 3

【输入样例2】

5 2 3
1 1
2 1

【输出样例2】

0 0 0 1 3

【输入样例3】

5 0 10

【输出样例3】

0 0 0 0 0

【输入样例4】

5 0 0

【输出样例4】

1 0 0 0 0

【数据范围】

• $1 \leq N \leq 1000000$
• $0 \leq K \leq 10$
• $0 \leq M \leq 1000000000000000000$
• $0 \leq i_0 < \cdots < i_{K-1} \leq N - 1$
• $1 \leq a_{i_k} < 998244353$

【来源】

Library Checker（yosupo06） pow_of_formal_power_series_sparse