题目描述

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

$$ \begin{aligned} xk &= 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(x1), \cdots , f(x{n - 1}) $ 对 $ 10 ^ 6 + 3 $ 取模的值。

输入格式

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

输出格式

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

样例

input

3 1 2 3 4
0 1 2

output

136
2080
190036

数据范围与提示