给定 n,b,c,d,e n, b, c, d, e n,b,c,d,e 以及 a0,a1,…an−1 a_0, a_1, \ldots a_{n - 1} a0,a1,…an−1，定义
xk=b×c4k+d×c2k+ef(x)=∑i=0n−1aixi \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} xkf(x)=b×c4k+d×c2k+e=i=0∑n−1aixi请你求出 f(x0),f(x1),⋯,f(xn−1) f(x_0), f(x_1), \cdots , f(x_{n - 1}) f(x0),f(x1),⋯,f(xn−1) 对 106+3 10 ^ 6 + 3 106+3 取模的值。
第一行包括五个整数 n,b,c,d,e n, b, c, d, e n,b,c,d,e。
接下来一行包括 n n n 个整数，代表 a0,a1,⋯,an−1 a_0, a_1, \cdots , a_{n - 1} a0,a1,⋯,an−1。
n n n 行，第 i i i 行代表 f(xi−1) f(x_{i - 1}) f(xi−1)。
3 1 2 3 4
0 1 2
136
2080
190036
| 测试点编号 | n≤ n \leq n≤ | 特殊条件 |
|---|---|---|
| 1 | 500 500 500 | |
| 2 | 2000 2000 2000 | |
| 3 | 10000 10000 10000 | |
| 4 | 20000 20000 20000 | |
| 5 | 30000 30000 30000 | |
| 6 | 40000 40000 40000 | |
| 7 | 50000 50000 50000 | b=0 b = 0 b=0 |
| 8 | 60000 60000 60000 | b=0 b = 0 b=0 |
| 9 | 60000 60000 60000 | |
| 10 | 60000 60000 60000 |