#pragma GCC optimize("Ofast", "inline")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;

using ll = long long;   using poly = vector<int>;   
const int N = 10010, mod = 1e9 + 7, SZ = (1 << 18) + 5;
static char buf[SZ], *bgn = buf, *til = buf;
char getc() {
    if(bgn == til)  bgn = buf, til = buf + fread(buf, 1, SZ, stdin);
    return bgn == til ? EOF : *bgn++;
}
template<typename T>
void read(T &x) {
    char ch = getc();  T fh = 0;   x = 0;
    while(ch < '0' || ch > '9')    fh |= (ch == '-'), ch = getc();
    while(ch >= '0' && ch <= '9')   x = x * 10 + ch - '0', ch = getc();
    x = fh ? -x : x;
}
template<typename Type, typename... argc>
void read(Type &x, argc &...args)   {read(x), read(args...);}
int n, m, w, u, v, a[N], ord[N], cnt, deg[N], iv[N], pw[N], sum[N], ans[N];
vector<int> edge[N];
poly f[N], tmp;
inline void Add(int &a, int b) {a += b, a >= mod && (a -= mod);}
inline int add(int a, int b)   {a += b, a >= mod && (a -= mod);    return a;}
ll qmi(ll a, ll b) {
    ll res = 1;
    for(; b; b >>= 1, a = a * a % mod)  if(b & 1)   res = res * a % mod;
    return res;
}
void topu() {
    queue<int> q;
    for(int i = 1; i <= n; ++i) if(!deg[i]) q.push(i);
    while(!q.empty()) {
        int x = q.front();  q.pop();
        ord[++cnt] = x;
        for(int y : edge[x]) {
            --deg[y];
            if(deg[y] == 0) q.push(y);
        }
    }
}
poly mul(poly &f, poly &g) {
    poly h(4, 0);
    h[0] = 1ll * f[0] * g[0] % mod;
    h[1] = (1ll * f[0] * g[1] + 1ll * f[1] * g[0]) % mod;
    h[2] = (1ll * f[0] * g[2] + 1ll * f[1] * g[1] + 1ll * f[2] * g[0]) % mod;
    h[3] = (1ll * f[0] * g[3] + 1ll * f[1] * g[2] + 1ll * f[2] * g[1] + 1ll * f[3] * g[0]) % mod;
    // for(int i = 0; i < 4; ++i)
    //     for(int j = 0; j + i < 4; ++j)  Add(h[i + j], 1ll * f[i] * g[j] % mod);
    return h;
}
void work(int v) {
    pw[0] = 1;
    for(int i = 1; i <= w; ++i) pw[i] = 1ll * pw[i - 1] * v % mod;
    for(int i = 1; i <= n; ++i) f[i].clear();
    for(int i = cnt; i > 0; --i) {
        int x = ord[i]; f[x].resize(4, 0);
        f[x][0] = 1, f[x][1] = pw[a[x]];
        for(int y : edge[x])    f[x] = mul(f[x], f[y]);
        Add(sum[v], f[x][3]);
    }
}
void mian(int T) {
    read(n, m, w);
    for(int i = 1; i <= n; ++i) edge[i].clear(), deg[i] = 0;
    tmp.clear(), cnt = 0, tmp.resize(w * 3 + 2, 0), tmp[0] = 1;
    for(int i = 0; i <= w * 3 + 1; ++i) sum[i] = ans[i] = 0;
    for(int i = 1; i <= n; ++i) read(a[i]);
    for(int i = 1; i <= m; ++i) read(u, v), edge[u].pb(v), ++deg[v];
    topu();
    for(int x = 1; x <= w * 3 + 1; ++x) work(x);
    for(int i = 1; i <= w * 3 + 1; ++i) {
        for(int j = w * 3 + 1; j > 0; --j)  tmp[j] = add(tmp[j - 1], mod - 1ll * i * tmp[j] % mod);
        tmp[0] = add(0, mod - 1ll * i * tmp[0] % mod);
    }
    for(int i = 1; i <= w * 3 + 1; ++i) {   
        poly nw = tmp;  int inv = qmi(i, mod - 2);
        nw[0] = 1ll * add(0, mod - nw[0]) * inv % mod;
        for(int j = 1; j < (int)nw.size(); ++j) Add(nw[j], mod - nw[j - 1]), nw[j] = 1ll * add(0, mod - nw[j]) * inv % mod;
        int val = sum[i];
        for(int j = 1; j <= w * 3 + 1; ++j) if(j != i)
            val = i > j ? (1ll * val * iv[i - j] % mod) : add(0, mod - 1ll * val * iv[j - i] % mod);
        for(int j = 1; j <= w * 3; ++j) Add(ans[j], 1ll * nw[j] * val % mod);
    }
    printf("Case #%d: ", T);
    for(int i = 1; i < w * 3; ++i) printf("%d ", ans[i]);
    printf("%d\n", ans[w * 3]);
}
int main() {
    #ifdef Kelly
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        freopen("err.txt", "w", stderr);
    #endif
    int T = 1;  read(T);
    iv[0] = 1;
    for(int i = 1; i <= 1201; ++i) iv[i] = qmi(i, mod - 2);
    for(int i = 1; i <= T; ++i) mian(i);
    return 0;   
}