#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
#define all(x) x.begin(), x.end()
const int inf = 1e4;

void solve() {
   int n, m, u, v;
   cin >> n >> m;
   vector <vector <bool>> adj(n + 1, vector <bool> (n + 1));
   vector <int> dp(1 << n, n + 1);
   dp[0] = 0;
   for (int i = 0; i < m; i++) {
      cin >> u >> v;
      adj[u][v] = true;
      adj[v][u] = true;
   }
   for (int k = 1; k < (1 << n); k++) {
      dp[k] = 1;
      for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {
            if ((k >> i) & (k >> j) & 1)
               if (adj[i + 1][j + 1] == false)
                  dp[k] = inf;
         }
   }
   for (int i = 0; i < (1 << n); i++) {
      for (int j = i; j > 0; j = (j - 1) & i) {
         dp[i] = min(dp[i], dp[j] + dp[i ^ j]);
      }
   }
   cout << dp[(1 << n) - 1] << '\n';

}

int main() {
#ifndef ONLINE_JUDGE
   freopen("E:\\inp.txt", "r", stdin);      freopen("E:\\outp.txt", "w", stdout);
#endif
   ios::sync_with_stdio(false);   cin.tie(NULL);   cout.tie(NULL);
   solve();

   return 0;
}
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline bool read(T&x){
x=0;char c=getchar();int f=1;while(!isdigit(c)&&(c!='-')&&(c!=EOF))c=getchar();
if(c==EOF)return 0;if(c=='-')f=-1,c=getchar();
while(isdigit(c)){x=(x<<1)+(x<<3)+(c&15);c=getchar();}x*=f;return 1;
}template<typename T,typename...Args>inline bool read(T&x,Args&...args){bool res=1;res&=read(x);res&=read(args...);return res;}
typedef long long LL;typedef unsigned long long u64;typedef unsigned u32;typedef long double LD;
#define il inline
#define pln putchar('\n')
#define For(i,a,b)  for(int i=(a),(i##i)=(b);i<=(i##i);++i)
#define Rep(i,n)    for(int i=0,(i##i)=(n);i<(i##i);++i)
#define Fodn(i,a,b) for(int i=(a),(i##i)=(b);i>=(i##i);--i)
const int M=1000000007,INF=0x3f3f3f3f;const long long INFLL=0x3f3f3f3f3f3f3f3fLL;
const int N=111;

/*********************数论*********************/
inline LL mul(LL a,LL b,LL p){const LL res=a*b-((LL)((LD)a*b/p)*p);return res<0?res+p:(res<p?res:res-p);}
inline LL fp(LL a,LL b,LL Mod){LL res=(Mod!=1);for(;b;b>>=1,a=a*a%Mod)if(b&1)res=res*a%Mod;return res;}
inline LL fpl(LL a,LL b,LL Mod){LL res=(Mod!=1);for(;b;b>>=1,a=mul(a,a,Mod))if(b&1)res=mul(res,a,Mod);return res;}
template<typename T>inline T gcd(T a,T b){while(b){T t=b;b=a%b;a=t;}return a;}template<typename T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
template<typename T>inline T exgcd(T a,T b,T&x,T&y){T m=0,n=1,t;x=1,y=0;while(b){t=m,m=x-a/b*m,x=t;t=n,n=y-a/b*n,y=t;t=b,b=a%b,a=t;}return a;}
inline LL Crt(LL a1,LL a2,LL mod1,LL mod2){LL u,v;const LL g=exgcd(mod1,mod2,u,v);if((a2-a1)%g)return -1;
const LL m12=abs(lcm(mod1,mod2)),res=(mul(mod1,mul(u,((a2-a1)/g),m12),m12)+a1)%m12;return res<=0?res+m12:res;/*求最小正数解还是非负解*/}
/*********************数论*********************/
LL n,m,k,d[N];
struct Mat{
	LL a[N][N];
	Mat(){memset(a,0,sizeof a);}
	void set(){for(int i=1;i<=n;++i)a[i][i]=1;}
	Mat operator*(const Mat&b)const{
		Mat res;
		for(int i=1;i<=n;++i)for(int k=1;k<=n;++k)for(int j=1;j<=n;++j)res.a[i][j]=(res.a[i][j]+(a[i][k]*b.a[k][j])%M)%M;
		return res;
	}
	Mat pow(LL b)const{
		Mat a=(*this),res;
		for(res.set();b;b>>=1,a=a*a)if(b&1)res=res*a;
		return res;
	}
};


LL a[N],mp[N][N];

LL im;

inline void init(){
	read(n,m,k);im=fpl(2ll*m,M-2,M);
	For(i,1,n)read(a[i]);
	For(i,1,m){
		int u,v;read(u,v);mp[u][v]=1;mp[v][u]=1;++d[u];++d[v];
	}
	For(i,1,n)mp[i][i]=mul((2ll*m-d[i]),im,M);
	For(i,1,n)For(j,1,i-1){
		if(mp[i][j]==0)continue;
		mp[i][j]=mp[j][i]=im;
	}
}	
LL ans[N];
inline void solve(){
	Mat f;
	For(i,1,n)For(j,1,n)f.a[i][j]=mp[i][j];
	f=f.pow(k);
	For(i,1,n)For(j,1,n)ans[i]=(ans[i]+mul(a[j],f.a[j][i],M))%M;
	For(i,1,n)ans[i]=(ans[i]+M)%M;
	For(i,1,n)printf("%lld\n",ans[i]);
}
signed main(){
	init();solve();
	return 0;
}