Problem Statement

Let $p = 1009$.
For the integers $K_0, K_1, \cdots, K_M$ given in the input, each at least $0$ and less than $p$, let $K := \sum_{j=0}^M K_j p^j$.
For the non-negative integers $A_{1,0}, \cdots, A_{1,N}$ given in the input, define $A_{k, 0}, \cdots, A_{k, N}$ inductively by the following operation:

$A_{k+1, n} := \sum_{i = 0}^{n} A_{k, i}A_{1, n-i}$

Output $A_{K, 0}, \cdots, A_{K, N}$ modulo $p$, in this order.

Input

$M \ N$
$K_0 \ \cdots \ K_M$
$A_{1, 0} \ \cdots \ A_{1, N}$

$0 \leq M < 4 \times 10^5,$
$0 \leq N < 2 \times 10^3,$
$0 \leq K_m < p \ (m = 0, \cdots, M, \ K_M \neq 0),$
$0 \leq A_{1, n} < p \ (n = 0, \cdots, N),$

Output

Output $A_{K, 0}, \cdots, A_{K, N}$ modulo $p$, in this order, separated by single spaces.

Sample

0 0
1
789

789

0 3
3
1 1008 0 0

1 1006 3 1008

1 5
99 100
1 2 3 4 5 6

1 198 530 691 669 390