Dane są $n$, $m$, $a$, $b$, $c$. Definiujemy $f_0(x)=1$, a dla $k>0$, $f_k(x)=\sum_{i=0}^x (a i^2 + b i + c) f_{k-1}(i)$. Dla każdej liczby całkowitej $i$ takiej, że $0 \le i < n$, oblicz wartość $f_i(m)$ modulo $1004535809$.

Wejście

W jednym wierszu pięć nieujemnych liczb całkowitych $n$, $m$, $a$, $b$, $c$.

Wyjście

$n$ wierszy, w każdym wierszu jedna liczba całkowita; liczba w $i$-tym wierszu (licząc od 1) oznacza wartość $f_{i-1}(m)$ modulo $1004535809$.

Przykład

Przykład 1

5 10 0 1 2

Wyjście 1

1
77
3289
103103
2650648

Uwagi

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

Ograniczenia