给定$n$，$m$，$a$，$b$，$c$。定义$f_0(x)=1$，对于$k>0$，$f_k(x)=\sum_{i=0}^x (a i^2 + b i + c) f_{k-1}(i)$。对于$0 \le i < n$的整数$i$，求出$f_i(m)$模$1004535809$的值。
输入格式
一行五个非负整数$n$，$m$，$a$，$b$，$c$。
输出格式
$n$行，每行一个整数，第$i$行的整数表示$f_{i-1}(m)$模$1004535809$的值。
样例数据
样例输入
5 10 0 1 2
样例输出
1 77 3289 103103 2650648
样例解释
$f_0(x) = 1$
$f_1(x) = \frac{1}{2} x^2 + \frac{5}{2} x + 2$
$f_2(x) = \frac{1}{8} x^4 + \frac{17}{12} x^3 + \frac{43}{8} x^2 + \frac{97}{12} x + 4$
$f_3(x) = \frac{1}{48} x^6 + \frac{19}{48} x^5 + \frac{47}{16} x^4 + \frac{175}{16} x^3 + \frac{517}{24} x^2 + \frac{127}{6} x + 8$
$f_4(x) = \frac{1}{384} x^8 + \frac{7}{96} x^7 + \frac{491}{576} x^6 + \frac{1307}{240} x^5 + \frac{23971}{1152} x^4 + \frac{1557}{32} x^3 + \frac{19537}{288} x^2 + \frac{2053}{40} x + 16$
数据范围
数据编号 |
$n$ |
$m$ |
$a$ |
$b$ |
$c$ |
|---|---|---|---|---|---|
0 |
$2000$ |
$\le 2000$ |
$\le 10^9$ |
$\le 10^9$ |
$\le 10^9$ |
1 |
$300$ |
$\le 10^9$ |
|||
2 |
$1000$ |
||||
3 |
$2000$ |
||||
4 |
$250000$ |
$0$ |
$0$ |
||
5 |
$\le 2000$ |
$\le 10^9$ |
$\le 10^9$ |
||
6 |
$\le 50000$ |
||||
7 |
$50000$ |
$\le 10^9$ |
$0$ |
$1$ |
$0$ |
8 |
$\le 10^9$ |
$\le 10^9$ |
|||
9 |
$250000$ |
$1$ |
$0$ |
||
10 |
$\le 10^9$ |
||||
11 |
$\le 10^9$ |
||||
12 |
$50000$ |
$1$ |
$0$ |
$0$ |
|
13 |
$\le 10^9$ |
$\le 10^9$ |
$\le 10^9$ |
||
14 |
$100000$ |
$1$ |
$0$ |
$0$ |
|
15 |
$\le 10^9$ |
$\le 10^9$ |
|||
16 |
$\le 10^9$ |
||||
17 |
$250000$ |
$1$ |
$0$ |
$0$ |
|
18 |
$\le 10^9$ |
$\le 10^9$ |
|||
19 |
$\le 10^9$ |