P12771 [POI 2018 R3] 多项式 Polynomial

翻译来自于 [LibreOJ](https://loj.ac/p/5079)。

**题目译自 [XXV Olimpiada Informatyczna — III etap](https://sio2.mimuw.edu.pl/c/oi25-3/dashboard/) [Wielomian](https://szkopul.edu.pl/problemset/problem/9JvSAnyf5d1FlPAEXEdUAtCz/statement/)** Bajtazar 在数学课上行为不端，作为惩罚，他需计算一个具有 $n$ 个整数系数的长多项式 $W$： $$ W(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_{n-2} x^{n-2} + a_{n-1} x^{n-1} $$ 在点 $q^1, q^2, \ldots, q^n$ 处的取值。为便于老师检查，他需先给出这些取值之和除以 $m$ 的余数，再给出各取值除以 $m$ 的余数。 Bajtazar 不仅调皮，还很懒惰，他请你帮忙，自己却跑去派对了。临走前，他提醒你：$n$ 是 $2$ 的幂，且 $q^n$ 除以 $m$ 的余数为 $1$（即 $q^n \bmod m = 1$）。他认为这些性质可大幅减少计算量。

第一行包含三个整数 $n, m, q$（$n \geq 1$，$n$ 为 $2$ 的幂，$2 \leq m \leq 10^9$，$1 \leq q < m$，$q^n \bmod m = 1$）。 第二行包含 $n$ 个整数 $a_0, a_1, \ldots, a_{n-1}$ $(0 \leq a_i \leq 10^9)$，表示多项式系数。

第一行输出一个整数，表示多项式 $W$ 在点 $q^1, q^2, \ldots, q^n$ 的取值之和除以 $m$ 的余数。 第二行输出 $n$ 个整数，表示 $W(q^1), W(q^2), \ldots, W(q^n)$ 除以 $m$ 的余数，空格分隔。

**样例 1 解释** 多项式为 $W(x) = 3 + 2x + 2x^2 + x^3$，其在各点取值为 $W(5) = 188$，$W(5^2) = 16928$，$W(5^3) = 1984628$，$W(5^4) = 244923128$。第一行输出 $188 + 16928 + 1984628 + 244923128 = 246924872$ 除以 $13$ 的余数，即 $12$。第二行输出各取值除以 $13$ 的余数：$188 \bmod 13 = 6$，$16928 \bmod 13 = 2$，$1984628 \bmod 13 = 9$，$244923128 \bmod 13 = 8$。 **附加样例** 1. $n=8, m=10, q=3$。 2. $n=256, m=10^9, q=m-1$。 3. $n=2^{13}, m=17, q=6$。 4. $n=2^{20}, m=1114129, q=2$。 若和正确但某取值错误，程序可获得 $40\%$ 的分数，且第二行需输出 $n$ 个 $[0, m-1]$ 范围的数。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n \leq 2^{10}$ | $17$ | | $2$ | $n \leq 2^{15}$ | $9$ | | $3$ | $n \leq 2^{20}$ | $74$ |