题目描述

给定 $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