Polynomial

Polynomial P(x) = a_0 + a_1x + a_2x^2 + ... + a_{n-1}x^{n-1} given set of coefficients a_0, a_1, ..., a_{n-1}.

Required to calculate the value of this polynomial modulo m for all integer x from 0 to a given number k.

Input

In the first line of the input file contains the numbers n, k and m (1 ≤ n ≤ 2000, 1 ≤ k ≤ 200000, 1 ≤ m ≤ 10^9). The second line contains the coefficients of a_0, a_1, ..., a_{n-1} — non-negative integers not exceeding 10^9.

Output

The output file output k+1 number - the remnants of the division of the values of P(0), P(1), ..., P(k) on m.

Examples