#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include #include #include #include using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i void chmin(A& l, const A& r){ if(r < l) l = r; } template void chmax(A& l, const A& r){ if(l < r) l = r; } using namespace std; #include //using Modint = atcoder::static_modint<998244353>; using Modint = atcoder::static_modint<1009>; void testcase(){ int P = 1009; i64 M, N; cin >> M >> N; vector K(M+1); rep(i,M+1) cin >> K[i]; vector A(N+1); rep(i,N+1){ int a; cin >> a; A[i] = a; } auto conv = [](vector a, vector b, int n) -> vector { vector res(n); rep(i,n) rep(j,n-i) if(i+j vector { if(x == 0){ vector R(n); if(n >= 1) R[0] = 1; return R; } auto V = powa(powa, n, x/2); auto W = conv(V, V, n); if(x % 2 == 1) W = conv(W, vector(A.begin(), A.begin()+n), n); return W; }; auto solve = [&](auto& solve, int n, int m) -> vector { if(n == 0){ Modint ans = 1; for(int k=M; k>=m; k--){ ans *= A[0].pow(K[k]); } return vector(1, ans); } if(m == M){ return powa(powa, n+1, K[m]); } auto re = solve(solve, n/P, m+1); vector res(n+1); rep(i,re.size()) res[i*P] = re[i]; res = conv(res, powa(powa, n+1, K[m]), n+1); return res; }; auto ans = solve(solve, N, 0); rep(i,N+1){ if(i) cout << ' '; cout << ans[i].val(); } cout << '\n'; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); testcase(); return 0; }