# include <stdio.h>

# include <string.h>

# include <iostream>

# include <algorithm>

// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int N = 1e3 + , H =  + ;

const int mod = 1e9+;

int n, L, w[N], inv2;

int f[N][H];

int ans[H];

int head[N], nxt[N + N], to[N + N], tot = ;

inline void add(int u, int v) {

    ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v;

}

inline void adde(int u, int v) {

    add(u, v), add(v, u);

}

inline int pwr(int a, int b) {

    int ret = ;

    while(b) {

        if(b&) ret = 1ll * ret * a % mod;

        a = 1ll * a * a % mod;

        b >>= ;

    }

    return ret;

}

int s[H], t[H];

inline void FWT(int *a, int op) {

    if(op) {

        for (int len = ; len <= L; len<<=) {

            int m = len >> ;

            for (int *p = a; p != a+L; p += len) {

                for (int k=; k<m; ++k) {

                    int x = p[k], y = p[k+m];

                    p[k] = 1ll * (x+y) * inv2 % mod;

                    p[k+m] = 1ll * (x-y+mod) * inv2 % mod;

                }

            }

        }

    } else {

        for (int len = ; len <= L; len<<=) {

            int m = len >> ;

            for (int *p = a; p != a+L; p += len) {

                for (int k=; k<m; ++k) {

                    int x = p[k], y = p[k+m];

                    p[k] = (x+y) % mod;

                    p[k+m] = (x-y+mod) % mod;

                }

            }

        }

    }

}

inline void FWT_combine(int *A, int *B) {

    for (int i=; i<L; ++i) s[i] = A[i], t[i] = B[i];

    FWT(s, ); FWT(t, );

    for (int i=; i<L; ++i) s[i] = 1ll * s[i] * t[i] % mod;

    FWT(s, );

    for (int i=; i<L; ++i) (A[i] += s[i]) %= mod;

}

inline void dfs(int x, int fa = ) {

    for (int j=; j<L; ++j) f[x][j] = ;

    f[x][w[x]] = ;

    for (int i=head[x]; i; i=nxt[i]) {

        if(to[i] == fa) continue;

        dfs(to[i], x);

        FWT_combine(f[x], f[to[i]]);

    }

    for (int j=; j<L; ++j) (ans[j] += f[x][j]) %= mod;

}

inline void sol() {

    tot = ;

    memset(head, , sizeof head);

    memset(ans, , sizeof ans);

    cin >> n >> L;

    for (int i=; i<=n; ++i) scanf("%d", w+i);

    for (int i=, u, v; i<n; ++i) {

        scanf("%d%d", &u, &v);

        adde(u, v);

    }

    dfs();

    printf("%d", ans[]);

    for (int i=; i<L; ++i) printf(" %d", ans[i]);

    puts("");

}

int main() {

    int T; cin >> T;

    inv2 = pwr(, mod-);

    while(T--) sol();

    return ;

}