QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100

# 621. 多项式指数函数

统计

题目描述

给定多项式 $A(z)=\sum^{n-1}_{i=0} a_ix^i$,求 $\exp A(z) \bmod {z^n} = \sum^{n-1}_{i=0} c_iz^i$

输入格式

输入的第一行包含一个整数 $n$。

接下来一行,包含 $n$ 个整数 $a_0,a_1,\cdots,a_{n-1}$。保证 $a_0=0$。

输出格式

输出一行 $n$ 个整数,表示 $c_0,c_1,\cdots,c_{n-1}$。

样例数据

样例输入

6
0 1 2 3 4 5

样例输出

1 1 499122179 166374064 291154613 690452363

子任务

对于所有数据,$1 \leq n \leq 10^6$。

测试点 $n$
$1$ $100$
$2$ $5 \times 10^3$
$3$ $3 \times 10^4$
$4$ $10^5$
$5$ $10^6$