2181: Evaluation

x_k=b*c^(2k)+d
F(x)=a₀x₀+a₁x₁+a₂x₂+...+a_n-1x_n-1
Given n, b, c, d, a₀, ..., a_n-1, calculate F(x₀), ..., F(x_n-1).

There is only one test case.
First line, four integers, n, b, c, d.
Second line, n integers, a₀, ..., a_n-1.

1<=n<=10⁵
1<= b, c, d <=10⁶
0<=a_i<=10⁶

n lines. i-th line contains one integer, F(x_i-1).
Since the answers may be very large, you should output them modulo 10⁶+3.

2 1 2 3
0 1

4
7