Guess the Formula Quiz Game

Time limit3sMemory limit1024 MB

Summary

Given f(x) mod p for x = 1 to p-1, recover the coefficients a_1 to a_(p-1) in the range 0 to p-1 of f(x) = sum of a_i * i^x mod p.

Level: Hard8 of 10
Topics: Number theory, Math, Divide and conquer
Solved: No attempts yet

Problem

Siru and Lucy, who failed their number theory exam, went deep into the mountains to learn number theory from ahgus, a master of the subject. ahgus decided to take disciples through a quiz game.

He has a prime $p$ that he cherishes and the following function.

$f(x) = \sum\_{i=1}^{p-1} a\_{i}i^{x} \, (0 \leq a\_{i} \leq p-1)$

He told them the remainder of each function value $f(1)$ , $f(2)$ , $\cdots$ , $f(p-1)$ when divided by $p$ . He said that only the person who can guess his beloved function is qualified to become his disciple.

Help Siru and Lucy compute the function.

Input

The first line contains the prime $p$ . The second line contains the remainders of $f(1)$ , $f(2)$ , $\cdots$ , $f(p-1)$ when each is divided by $p$ , separated by spaces.

Output

Print $a\_1$ , $a\_2$ , ..., $a\_{p-1}$ . It can be proven that every $a\_i$ always exists uniquely and is an integer.

Constraints

$p \leq 300,000$

Examples2

Example 1
Input
```
5
0 0 4 0
```
Expected output
```
1 2 3 4
```
Example 2
Input
```
7
6 6 0 4 2 2
```
Expected output
```
1 5 0 2 5 3
```