Description

给定n,b,c,d,e以及A0,A1,···,An−1，定义

x ~k~ =b×c^ ^4k^ +d×c^ ^2k^ +e

f(x)=Sigma(A~i~x^ ^i^ ),0<=i<=n-1

请你求出f(x ~0~ ),f(x ~1~ ),···,f(x ~n−1~ )对10^6+3取模的值。

Format

Input

第一行包括五个整数n,b,c,d,e。

接下来一行包括n个整数，代表a ~0~ ,a ~1~ ,···,a ~n−1~ 。

N<=60000,保证给出的数字都为整数且均在 [0, 10^6]

Output

N行，第i行代表f(x ~i−1~ )

Samples

3 1 2 3 4
0 1 2

136
2080
190036