$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$ で割った余りを求めよ。
入力
1行に5つの非負整数 $n$，$m$，$a$，$b$，$c$ が与えられる。
出力
$n$ 行出力せよ。第 $i$ 行には $f_{i-1}(m)$ を $1004535809$ で割った余りを出力せよ。
入出力例
入力 1
5 10 0 1 2
出力 1
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$ |