#include <bits/stdc++.h>

using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define debug(output) if(debugFlag)cout<<#output<<"= "<<output<<endl
using lint = long long;
typedef pair<int,int> P;
const bool debugFlag=true;
const lint linf=1e18+7;
const lint inf=1e9+7;
const int MOD=1000000007;

signed main(){
  int n,m;cin>>n>>m;
  vector<set<int>> edge(n);
  rep(i,m){
      int a,b;cin>>a>>b;
      --a;--b;
      edge[a].insert(b);
      edge[b].insert(a);
  }
  lint res=0;
  auto binary_graph=[&](vector<int>const& h,int& sm)->bool{
      int hn=h.size();
      vector<int> memo(hn,0);
      vector<vector<int>> edge2(hn);
      rep(i,hn){
          for(int j=i+1;j<hn;++j){
              if(edge[h[i]].find(h[j])!=edge[h[i]].end()){
                  edge2[i].push_back(j);
                  edge2[j].push_back(i);
              }
          }
      }
      rep(st,hn){
          if(memo[st]>0)continue;
          queue<int> que;
          que.push(st);
          ++sm;
          memo[st]=1;
          while(!que.empty()){
              int no=que.front();que.pop();
              for(auto& e:edge2[no]){
                  if(memo[e]==0){
                      memo[e]=3^memo[no];
                      que.push(e);
                  }
                  else if(memo[e]==memo[no])return false;
              }
          }
      }
      return true;
  };
  rep(bit,(1<<n)){
      vector<int> g,h;
      rep(i,n){
          if(bit&(1<<i))g.push_back(i);
          else h.push_back(i);
      }
      bool flag=false;
      rep(i,g.size()){
          for(int j=i+1;j<g.size();++j){
              if(edge[g[i]].find(g[j])!=edge[g[i]].end())flag=true;
          }
      }
      if(flag)continue;
      int cnt=0;
      if(binary_graph(h,cnt)){
          res+=(1<<cnt);
          //debug(bit);
          //debug((1<<cnt));
      }
  }
  cout<<res<<"\n";
  return 0;
}
/*
5 4
1 2
2 3 
3 4
4 5
18
*/
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
//#include<atcoder/all>
//using namespace atcoder;

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int mod = 1e9 + 7;
int dp[4][100][100];
int AB[200], *A = AB, *B = AB + 100;
constexpr ll modpow(ll A, ll B) {
	ll kotae = 1;
	while (B > 0) {
		if (B & 1) kotae = kotae * A % mod;
		A = A * A % mod;
		B >>= 1;
	}
	return kotae;
}
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	int N, M, K;
	cin >> N >> M >> K;
	rep(i, N) {
		cin >> A[i];
	}
	auto mae1 = dp[0], mae2 = dp[1], ato1 = dp[2], ato2 = dp[3];
	rep(i, N) mae1[i][i] = 1;
	int are = modpow(2 * M, mod - 2);

	rep(i, M) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		(mae1[x][x] += mod - are) %= mod;
		(mae1[x][y] += are) %= mod;
		(mae1[y][x] += are) %= mod;
		(mae1[y][y] += mod - are) %= mod;
	}
	rep(x, N) rep(y, N) mae2[y][x] = mae1[x][y];

	rep(i, 30) {
		if (K >> i & 1) {
			rep(i, N) {
				ll tmp = 0;
				rep(j, N) tmp += (ll)mae1[i][j] * A[j] % mod;
				B[i] = tmp % mod;
			}
			swap(A, B);
		}

		rep(x, N) rep(y, N) {
			auto tmp1 = mae1[x];
			auto tmp2 = mae2[y];
			unsigned long long tmp = 0;
			rep(z, N) {
				tmp += *tmp1++ * (ll)*tmp2++;
				if (!(z & 15)) tmp %= mod;
			}
			ato2[y][x] = (ato1[x][y] = tmp % mod);
		}
		swap(mae1, ato1);
		swap(mae2, ato2);
	}

	rep(i, N) co(A[i]);


	Would you please return 0;
}