题目描述

素数 $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}$ の値をこの順に空白区切りで出力せよ。

なお、解は必ず存在することが示せる。複数の解が存在する場合は、そのうちのどれを出力してもよい。

题目大意

给出一个质数 $p$ 和长度为 $p$ 的数列 $a_0,\dots,a_{p-1}$，数列 $a$ 的每一项均为 $0$ 或 $1$。

要求找到一个次数不超过 $p-1$ 的多项式 $b$，使得 $f(x)=b_{p-1}x^{p-1}+b_{p-2}x^{p-2}+\dots+b_0$ 满足以下条件：

• 对于任意的正整数 $i$（$0 \le i \le p-1$），$0 \le b_i \le p-1$ 且 $b_i$ 为整数。

• 对于任意的正整数 $i$（$0 \le i \le p-1$），$f(i) \equiv a_i \pmod p$。

保证 $2 \le p \le 2999$。可以证明一定有解，输出任意一组解即可。

2
1 0

1 1

3
0 0 0

0 0 0

5
0 1 0 1 0

0 2 0 1 3

提示

制約

• $2\ \leq\ p\ \leq\ 2999$
• $p$ は素数である。
• $0\ \leq\ a_i\ \leq\ 1$

Sample Explanation 1

$f(x)\ =\ x\ +\ 1$ は以下のように条件を満たします。 - $f(0)\ =\ 0\ +\ 1\ =\ 1\ \equiv\ 1\ \pmod\ 2$ - $f(1)\ =\ 1\ +\ 1\ =\ 2\ \equiv\ 0\ \pmod\ 2$

Sample Explanation 2

$f(x)\ =\ 0$ も有効な出力です。