Даны целые числа $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)$. Для каждого целого числа $i$, где $0 \le i < n$, найдите значение $f_i(m)$ по модулю $1004535809$.

Входные данные

Одна строка, содержащая пять неотрицательных целых чисел $n$, $m$, $a$, $b$, $c$.

Выходные данные

$n$ строк, в каждой из которых содержится одно целое число. Число в $i$-й строке (нумерация с 1) должно представлять значение $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$

Ограничения