说明

给定$n,b,c,d,e,a_0,a_1,\ldots ,a_{n-1}$，定义

求$f(x_0),f(x_1),\ldots f(x_{n-1})$ 对$10^6+3$取模的值。

输入格式

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

接下来一行包括$n$个整数，代表$a_0,a_1,\ldots,a_{n-1}$。

输出格式

$n$行，第$i$行代表$f(x_{i-1})$。

样例

3 1 2 3 4
0 1 2

136
2080
190036

数据规模与约定

对于$100\%$的数据：$n\le 6\times 10^4$。