题目描述

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

数据范围与提示