Polynomial Evaluation

Time limit1sMemory limit1024 MB

Summary

Given a polynomial of degree N and a prime P, print f(x) mod P for every x from 0 to P-1.

Level: Medium5 of 10
Topics: Number theory, Math, Array
Solved: No attempts yet

Problem

A polynomial $f(x) = a_Nx^N + \cdots + a_1x + a_0$ of degree $N$ and a prime $P$ are given. A prime is a number divisible only by $1$ and itself. $1$ is not prime.

Write a program that computes $f(0) \bmod P$ , $f(1) \bmod P$ , $\cdots$ , $f(P-1) \bmod P$ . Here $u \bmod v$ is the remainder when $u$ is divided by $v$ .

Input

The first line contains two integers $N$ and $P$ ( $0 \le N \le 10^6$ , $1 \le P \le 10^3$ , $P$ is prime), separated by a space.

The second line contains $N+1$ integers $a_N, \cdots, a_1, a_0$ ( $0 \le a_i \le 10^9$ ), separated by spaces.

Output

Print $P$ lines. The $i$ -th line contains $f(i-1) \bmod P$ .

Examples3

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

Example 3

Input

8 17
10 55 23 5 8 24 9 1 77

Expected output