模 p 多项式

题目描述

给定素数 $p$ 和一个长度为 $p$、由 $0$ 和 $1$ 组成的整数列 $a_0, \ldots, a_{p-1}$。

请找出一个满足以下条件的、次数不超过 $p-1$ 的多项式 $f(x) = b_{p-1} x^{p-1} + b_{p-2} x^{p-2} + \ldots + b_0$：

• 对每个 $i$ $(0 \leq i \leq p-1)$，$b_i$ 是满足 $0 \leq b_i \leq p-1$ 的整数
• 对每个 $i$ $(0 \leq i \leq p-1)$，$f(i) \equiv a_i \pmod p$

输入格式

输入按以下格式从标准输入给出：

$p$
$a_0$ $a_1$ $\ldots$ $a_{p-1}$

输出格式

按顺序用空格分隔输出满足条件的多项式 $f(x)$ 的其中一个的系数 $b_0, b_1, \ldots, b_{p-1}$。

可以证明解必然存在。如果存在多个解，输出其中任意一个均可。

样例

2
1 0

1 1

$f(x) = x + 1$ 满足条件，验证如下：

• $f(0) = 0 + 1 = 1 \equiv 1 \pmod 2$
• $f(1) = 1 + 1 = 2 \equiv 0 \pmod 2$

3
0 0 0

0 0 0

$f(x) = 0$ 也是有效的输出。

5
0 1 0 1 0

0 2 0 1 3

数据范围

• $2 \leq p \leq 2999$
• $p$ 是素数
• $0 \leq a_i \leq 1$

提示

答案不唯一，输出任意合法解即可。