任意模数 Chirp Z-Transform
题目描述
给定一个 $n$ 项多项式 $P(x)$ 以及 $c, m$，请计算 $P(c^0),P(c^1),\dots,P(c^{m-1})$。所有答案都对 $10^9+7$ 取模。
输入输出格式
输入格式
第一行三个正整数 $n,c,m$。
第二行 $n$ 个非负整数 $a_0,a_1,\dots,a_{n-1}$，由低到高表示 $P(x)$ 的系数。
输出格式
一行 $m$ 个正整数，第 $i$ 个数表示 $P(c^{i-1})$。
输入输出样例
输入样例 #1
6 108616 6
1 0 8 6 1 6输出样例 #1
22 772456230 866731294 299746576 978045696 394365866说明
对于 $100\%$ 的数据，$1\le n,m\le 6\cdot10^5,0\le c,a_i<10^9+7$.
| 测试点编号 | $n,m$ 限制 |
| :-----------: | :-----------: |
| $1$ | $n=m=1000$ |
| $2$ | $n=m=64000$ |
| $3$ | $n=m=5\cdot10^5$ |
| $4$ | $n=5\cdot10^5,m=6\cdot10^5$ |
| $5$ | $n=6\cdot10^5,m=5\cdot10^5$ |
出题人很遗憾由于精度和洛谷自带资料限制无法开到 $10^6$。
提示：$7$ 次 $FFT$ 可能过不了。
提示：出题人没有用 `long double`。