Pow of Formal Power Series

AC一覧

Problem Statement問題文

You are given a formal power series $f(x) = \sum_{i=0}^{N-1} a_i x^i \in \mathbb{F}_{998{,}244{,}353}[[x]]$ and a positive integer $M$. Calculate the first $N$ terms of $(f(x))^M = \sum_{i=0}^{\infty} b_i x^i$.

Constraints制約

• $1 \leq N \leq 500{,}000$
• $1 \leq M \leq 10^{9}$
• $0 \leq a_i < 998{,}244{,}353$

Input入力

$N$ $M$
$a_0$ $a_1$ $\cdots$ $a_{N-1}$


Output出力

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


Sampleサンプル

# 1

4 3
0 0 9 12

0 0 0 0


# 2

2 2
1 1

1 2


Timelimit: 10 secs

Before submitting, please confirm terms and conditions