该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile6067.zip](file://AdditionalFile6067.zip?type=additional_file)

#6067. 「2017 山东一轮集训 Day3」第三题

标签: 传统 | 时间限制: 3000 ms | 内存限制: 256 MiB |

题目描述

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

$$\begin{aligned} x_k &= b \times c ^ {4k} + d \times c ^ {2k} + e \\ f(x) &= \sum\limits_{i = 0} ^ {n - 1} a_i x ^ i \end{aligned}$$

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

输入格式

第一行包括五个整数 $n, b, c, d, e$。
接下来一行包括 $n$ 个整数，代表 $a_0, a_1, \cdots , a_{n - 1}$。

输出格式

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

样例

输入

3 1 2 3 4
0 1 2

输出

136
2080
190036

数据范围与提示

测试点编号	$n \leq$	特殊条件
1	$500$
2	$2000$
3	$10000$
4	$20000$
5	$30000$
6	$40000$
7	$50000$	$b = 0$
8	$60000$
9
10