#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector<int> vi;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

int test_id ;
const int MAXN = 1e4 + 7 ;
const int MOD = 1e9 + 7 ;
const int MAXW = 402 ;

typedef complex<double> C;
typedef vector<double> vd;
void fft(vector<C>& a) {
	int n = sz(a), L = 31 - __builtin_clz(n);
	static vector<complex<long double>> R(2, 1);
	static vector<C> rt(2, 1);  // (^ 10% faster if double)
	for (static int k = 2; k < n; k *= 2) {
		R.resize(n); rt.resize(n);
		auto x = polar(1.0L, acos(-1.0L) / k);
		rep(i,k,2*k) rt[i] = R[i] = i&1 ? R[i/2] * x : R[i/2];
	}
	vi rev(n);
	rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
	rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int k = 1; k < n; k *= 2)
		for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
			// C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled)  /// include-line
			auto x = (double *)&rt[j+k], y = (double *)&a[i+j+k];        /// exclude-line
			C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]);           /// exclude-line
			a[i + j + k] = a[i + j] - z;
			a[i + j] += z;
		}
}
vd conv(vd& a, vd& b) {
	if (a.empty() || b.empty()) return {};
	vd res(sz(a) + sz(b) - 1);
	int L = 32 - __builtin_clz(sz(res)), n = 1 << L;
	vector<C> in(n), out(n);
	copy(all(a), begin(in));
	rep(i,0,sz(b)) in[i].imag(b[i]);
	fft(in);
	for (C& x : in) x *= x;
	rep(i,0,n) out[i] = in[-i & (n - 1)] - conj(in[i]);
	fft(out);
	rep(i,0,sz(res)) res[i] = imag(out[i]) / (4 * n);
	return res;
}

template<int M> vi convMod(const vi &a, const vi &b) {
	if (a.empty() || b.empty()) return {};
	vi res(sz(a) + sz(b) - 1);
	int B=32-__builtin_clz(sz(res)), n=1<<B, cut=int(sqrt(M));
	vector<C> L(n), R(n), outs(n), outl(n);
	rep(i,0,sz(a)) L[i] = C((int)a[i] / cut, (int)a[i] % cut);
	rep(i,0,sz(b)) R[i] = C((int)b[i] / cut, (int)b[i] % cut);
	fft(L), fft(R);
	rep(i,0,n) {
		int j = -i & (n - 1);
		outl[j] = (L[i] + conj(L[j])) * R[i] / (2.0 * n);
		outs[j] = (L[i] - conj(L[j])) * R[i] / (2.0 * n) / (C)1i;
	}
	fft(outl), fft(outs);
	rep(i,0,sz(res)) {
		ll av = ll(real(outl[i])+.5), cv = ll(imag(outs[i])+.5);
		ll bv = ll(imag(outl[i])+.5) + ll(real(outs[i])+.5);
		res[i] = ((av % M * cut + bv) % M * cut + cv) % M;
	}
	return res;
}


int n , m , lim ;
int a[ MAXN ] ;
vector < int > v[ MAXN ] ;
int dp[ MAXN ][ MAXW ] ;

int ans[ 3 * MAXW ] ;

void dfs ( int x ) {
    for ( int i = 0 ; i <= lim ; ++ i ) { dp[ x ][ i ] = 0 ; }
    dp[ x ][ a[ x ] ] = 1 ;
    for ( auto y : v[ x ] ) {
        dfs ( y ) ;
        for ( int j = 0 ; j <= lim ; ++ j ) {
            dp[ x ][ j ] = ( dp[ x ][ j ] + dp[ y ][ j ] ) % MOD ;
        }
    }
}

ll fastpow ( ll x , ll pw ) {
    ll ret = 1 ;
    while ( pw > 0 ) {
        if ( ( pw % 2 ) == 0 ) {
            x = ( x * x ) % MOD ;
            pw /= 2 ;
        }
        else {
            ret = ( ret * x ) % MOD ;
            -- pw ;
        }
    }
    return ret ;
}

void solve ( ) {
    ++ test_id ;
    cout << "Case #" << test_id << ": " ;
    cin >> n >> m >> lim ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
        v[ i ].clear ( ) ;
    }
    for ( int i = 0 ; i <= 3 * lim ; ++ i ) { ans[ i ] = 0 ; }
    for ( int i = 1 , x , y ; i <= m ; ++ i ) {
        cin >> x >> y ;
        v[ x ].push_back ( y ) ;
    }
    dfs ( 1 ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        vi one , two , three ;
        two.resize ( 2 * lim + 1 , 0 ) ;
        three.resize ( 3 * lim + 1 , 0 ) ;
        int sm = 0 ;
        for ( int j = 0 ; j <= lim ; ++ j ) {
            sm += min ( dp[ i ][ j ] , 3 ) ;
            one.push_back ( dp[ i ][ j ] ) ;
            two[ 2 * j ] = dp[ i ][ j ] ;
            three[ 3 * j ] = dp[ i ][ j ] ;
        }
        if ( sm < 3 ) { continue ; }
        vi wtf = convMod < MOD > ( one , one ) ;
        vi aux = convMod < MOD > ( wtf , one ) ;
        vi sub = convMod < MOD > ( two , one ) ;
        for ( int j = 0 ; j <= 3 * lim ; ++ j ) {
            ll add = ( aux[ j ] - 3 * sub[ j ] + 3LL * MOD + 2 * three[ j ] ) % MOD ;
            ans[ j ] = ( ans[ j ] + add ) % MOD ;
        }
    }
    ll inv = fastpow ( 6 , MOD - 2 ) ;
    for ( int i = 1 ; i <= 3 * lim ; ++ i ) {
        cout << ( ans[ i ] * inv ) % MOD ;
        if ( i != 3 * lim ) { cout << " " ; }
    }
    cout << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}