Polynomial Evaluation at Power Sequences

Given an (n)-term polynomial (P(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}) and two integers (c) and (m), compute (P(c^0), P(c^1), \dots, P(c^{m-1})) modulo (10^9+7).

inputFormat

The first line contains three integers (n), (c), and (m), where (n) is the number of terms of the polynomial (P(x)). The second line contains (n) integers (a_0, a_1, \dots, a_{n-1}) representing the coefficients of (P(x)).

outputFormat

Output (m) space-separated integers, where the (j)-th integer (0-indexed) is (P(c^j)) computed modulo (10^9+7).

sample

3 2 3
1 2 3

6 17 57