#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LLL __int128
#define pii pair<int, int>
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pil pair<int, LL>
#define fi first
#define se second
#define mkp make_pair
#define sz(x) (int)x.size()
#define ppc(x) __builtin_popcount(x)
#define pb push_back
using namespace std;
bool Med;

LL read() {
	LL s = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
		f = (ch == '-' ? -1 : 1), ch = getchar();
	while (ch >= '0' && ch <= '9')
		s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
	return s * f;
}

template<typename T> void chkmn(T &x, T y) {x = x > y ? y : x;}
template<typename T> void chkmx(T &x, T y) {x = x < y ? y : x;}

const int MAXN = 10005, mod = 1e9 + 7, inv6 = (mod + 1) / 6, inv2 = (mod + 1) / 2;

int qpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod, b >>= 1;
	}
	return res;
}

auto fplus = [](int x, int y) {return x + y < mod ? x + y : x + y - mod;};
auto fminus = [](int x, int y) {return x >= y ? x - y : x + mod - y;};
auto Fplus = [](int &x, int y) {x = fplus(x, y);};
auto Fminus = [](int &x, int y) {x = fminus(x, y);};

#define poly vector<int>

int n, m, w;
int a[MAXN], deg[MAXN];
vector<int> e[MAXN];
int ans[1205], f[MAXN], g[MAXN], h[MAXN], pw[1205], res[1205], dp[1205];

void chazhi(int *a, int n) {
	memset(dp, 0, sizeof dp);
	memset(res, 0, sizeof res);
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = i; j; j--) dp[j] = fminus(dp[j - 1], 1ll * dp[j] * i % mod);
		dp[0] = fminus(0, 1ll * dp[0] * i % mod);
	}
	for (int i = 1; i <= n; i++) {
		int coef = a[i], inv = qpow(i, mod - 2);
		for (int j = 1; j <= n; j++)
			if (i != j) coef = 1ll * coef * qpow(fminus(i, j), mod - 2) % mod;
		dp[0] = 1ll * dp[0] * fminus(0, inv) % mod;
		for (int j = 1; j <= n; j++) dp[j] = 1ll * fminus(dp[j - 1], dp[j]) * inv % mod;
		for (int j = 1; j < n; j++) Fplus(res[j], 1ll * dp[j] * coef % mod);
		for (int j = n; j; j--) dp[j] = fminus(dp[j - 1], 1ll * dp[j] * i % mod);
		dp[0] = fminus(0, 1ll * dp[0] * i % mod);
	}
}

void work(int id) {
	n = read(), m = read(), w = read();
	for (int i = 1; i <= n; i++) a[i] = read(), deg[i] = 0, e[i].clear();
	for (int i = 1; i <= m; i++) {
		int u = read(), v = read();
		e[u].pb(v), deg[v]++;
	}
	queue<int> q;
	vector<int> top;
	for (int i = 1; i <= n; i++)
		if (!deg[i]) q.push(i);
	while (!q.empty()) {
		int x = q.front();
		q.pop(), top.pb(x);
		for (int y : e[x])
			if (!--deg[y]) q.push(y);
	}
	for (int i = 1; i <= 3 * w + 1; i++) {
		ans[i] = 0, pw[0] = 1;
		for (int j = 1; j <= 3 * w; j++) pw[j] = 1ll * pw[j - 1] * i % mod;
		for (int j = n - 1; j >= 0; j--) {
			int x = top[j]; f[x] = pw[a[x]], g[x] = pw[2 * a[x]], h[x] = pw[3 * a[x]];
			for (int y : e[x]) Fplus(f[x], f[y]), Fplus(g[x], g[y]), Fplus(h[x], h[y]);
			Fplus(ans[i], (1ll * f[x] * f[x] % mod * f[x] % mod + 2 * h[x] % mod - 3ll * g[x] * f[x] % mod + mod) % mod);
		}
	}
	chazhi(ans, 3 * w + 1);
	printf("Case #%d: ", id);
	for (int i = 1; i <= 3 * w; i++) printf("%lld%c", 1ll * res[i] * inv6 % mod, " \n"[i == 3 * w]);
	// memset(f, 0, sizeof f);
	// for (int i = n - 1; i >= 0; i--) {
	// 	int x = top[i];
	// 	for (int y : e[x])
	// 		for (int j = 1; j <= w; j++) Fplus(f[x][j], f[y][j]);
	// 	Fplus(f[x][a[x]], 1);
	// }
	// for (int i = 1; i <= n; i++) {
	// 	for (int j = 1; j <= 3 * w; j++) num[j] = res[j] = 0;
	// 	for (int j = 1; j <= w; j++) num[j] = f[i][j];
	// 	for (int j = 1; j <= w * 2; j++)
	// 		for (int k = 0; k <= j; k++) Fplus(res[j], 1ll * num[k] * num[j - k] % mod);
	// 	for (int j = w * 3; j; j--) {
	// 		res[j] = 0;
	// 		for (int k = 1; k < j; k++) Fplus(res[j], 1ll * res[k] * num[j - k] % mod);
	// 	}
	// 	for (int j = 1; j <= w; j++) Fplus(res[3 * j], 2 * num[j] % mod);
	// 	for (int j = 1; j <= w; j++)
	// 		for (int k = 1; k <= w; k++)
	// 			Fminus(res[2 * j + k], 3ll * num[j] * num[k] % mod);
	// 	for (int j = 1; j <= w * 3; j++) Fplus(ans[j], 1ll * res[j] * inv6 % mod);
	// }
}

bool Mst;
signed main() {
	// freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);
	fprintf(stderr, "%.2lfMB\n", (&Med - &Mst) / 1048576.0);
	int T = read();
	for (int i = 1; i <= T; i++) work(i);
	return 0;
}