Sequence Reconstruction#3695
Sign in

Sequence Reconstruction

0.5 seconds
256 megabytes
Easy

The sequence consists of non-negative integers a_i (1 \le i \le n), each of which is strictly less than some prime number . Based on this sequence, we construct a sequence so that its -th (1 \le i \le n) element satisfies the following condition:

b_i \equiv a_1i^1 + a_2i^2 + ... + a_{n-1}i^{n-1} + a_ni^n \pmod{p}

You are given the values of b_i (1 \le i \le n) and . You need to reconstruct the sequence .

Input

The first line of the input file contains a prime number (2 \le p < 10^9) and an integer (1 \le n \le 500). The second line contains non-negative integers b_1, b_2, ..., b_n, each of which does not exceed 10^9.

Output

If no sequences satisfy the problem's conditions, print a single number . Else, print numbers a_1, a_2, ..., a_n (0 \le a_i < p). If there are multiple possible sequences, print any of them.

Examples

Example 1

Loading
Loading