#include<bits/stdc++.h>
#define int long long
#define ld long double
#define fi first
#define se second
#define vll vector<int>
#define pii pair<int,int>
#define pb push_back
#define sz(v) (int)(v).size()
#define inf (int)(1e18)
#define md (int)(1e9+7)
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(int i=a;i<b;++i)
using namespace std;

const int M = 2e5 + 10;

#define K 101

int ex(int a,int b=md-2){
	int ans=1;
	while(b) {
		if(b&1) ans=(ans*a)%md;
		a=(a*a)%md,b/=2;
	}
	return ans;
} 
inline int add(int a,int b){
	a+=b;
	if(a>=md) a-=md;
	return a;
}
inline int sub(int a,int b){
	a-=b;
	if(a<0) a+=md;
	return a;
}
inline int mul(int a,int b){
	return (a*b)%md;
}

int f[M],iv[M];
int C(int n,int r){
	if(n<r) return 0;
	return mul(f[n],mul(iv[r],iv[n-r]));
}

void init(){
	f[0]=1;
	for(int i=1;i<M;++i) {
		f[i]=mul(i,f[i-1]);
	}
	iv[M-1]=ex(f[M-1]);
	for(int i=M-2;i>=0;--i) {
		iv[i]=mul(i+1,iv[i+1]);
	}
}


struct mat{
	int data[K][K]={0};
};

mat operator*(mat &a, mat &b){
	mat c;
	for(int i=0;i<K;++i)for(int j=0;j<K;++j){
		c.data[i][j]=0;
		for(int k=0;k<K;++k) {
			c.data[i][j]+=(a.data[i][k]*1ll*b.data[k][j])%md;
			if(c.data[i][j]>=md) c.data[i][j]-=md;
		}
	}
	return c;
}

mat operator^(mat &a,int b){
	mat c;
	for(int i=0;i<K;++i)for(int j=0;j<K;++j) c.data[i][j]=(i==j);
	while(b){if(b&1)c=c*a;a=a*a;b/=2;}
	return c;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
   	
   	int n,m,k;
   	cin>>n>>m>>k;
   	mat A;
   	int a[n];
   	rep(i,0,n) cin>>a[i];
   	int p=ex(mul(m,2));
   	rep(i,0,n)rep(j,0,n) {
   		A.data[i][j]=i==j;
   	}
   	rep(i,0,m) {
   		int u,v;
   		cin>>u>>v;
   		u--,v--;
   		A.data[u][v]=add(A.data[u][v],p);
   		A.data[v][u]=add(A.data[v][u],p);
   		A.data[u][u]=sub(A.data[u][u],p);
   		A.data[v][v]=sub(A.data[v][v],p);
   	}
   	A=A^k;
   	mat B;
   	rep(i,0,n) {
   		rep(j,0,n) B.data[i][j]=a[j];
   	}
   	A=B*A;
   	rep(i,0,n) cout<<A.data[i][i]<<"\n";
   	
   	
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=5005,mod=998244353;
int n,m,ans,f[N][2],g[N][2];
inline int add(int a,int b){
	a+=b;
	return a<mod?a:a-mod;
}
inline int dec(int a,int b){
	a-=b;
	return a<0?a+mod:a;
}
inline int mul(int a,int b){
	return 1LL*a*b%mod;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(f));
		f[0][0]=1;
		g[0][0]=0;
		for(int j=1;j<=n;j++){
			f[j][0]=add(mul(f[j-1][0],m-1),mul(f[j-1][1],i-1));
			g[j][0]=add(mul(g[j-1][0],m-1),mul(g[j-1][1],i-1));
			f[j][1]=add(f[j-1][0],mul(f[j-1][1],m-i+1));
			if(j==n){
				j++;
				j--;
			}
			g[j][1]=add(g[j-1][0],f[j-1][0]);
			g[j][1]=add(g[j][1],mul(g[j-1][1],m-i+1));
		}
		ans=add(ans,add(g[n][0],g[n][1]));
	}
	printf("%d\n",ans);
	return 0;
}