#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
#define vec vector<ll>
#define mat vector<vector<ll> >
#define fi first
#define se second
#define double long double
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
//typedef long double ld;
typedef complex<double> Complex;
const ll INF=1e9+7;
const ll MOD=INF;
const ll inf=INF*INF;
const ll mod=MOD;
const ll MAX=270010;

//二分累乗

ll rui(ll a,ll b){
    ll res=1;
    ll x=a;
    while(b){
        if(b&1)res=res*x%mod;
        x=x*x%mod;
        b/=2;
    }
    return res;
}

//行列累乗
mat mul(mat &A,mat &B){
    mat C(A.size(),vec(B[0].size()));
    rep(i,A.size()){
        rep(j,B[0].size()){
            rep(k,B.size()){
                C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%mod)%mod;
            }
        }
    }
    return C;
}
mat pow(mat A,ll k){
    mat B(A.size(),vec(A.size()));
    rep(i,A.size())B[i][i]=1;
    while(k>0){
        if(k&1)B=mul(B,A);
        A=mul(A,A);
        k>>=1;
    }
    return B;
}

signed main(){
    ll n,m,k;cin>>n>>m>>k;

    vector<ll>a(n);
    rep(i,n)cin>>a[i];
    vector<vector<ll> >s(n,vector<ll>(n));
    ll invm=rui(m*2LL%mod,mod-2);
    rep(i,m){
        ll x,y;cin>>x>>y;
        x--;y--;
        s[x][x]=(s[x][x]-invm)%mod;
        s[y][y]=(s[y][y]-invm)%mod;
        s[x][y]=(s[x][y]+invm)%mod;
        s[y][x]=(s[y][x]+invm)%mod;
    }
    rep(i,n){
        s[i][i]=(s[i][i]+1)%mod;
    }
    vector<vector<ll> >d=pow(s,k);
    rep(i,n){
        ll ans=0;
        rep(j,n){
            ans=(ans+a[j]*d[i][j]%mod)%mod;
        }
        if(ans<0)ans+=mod;
        cout<<ans<<endl;
    }
}
#include <bits/stdc++.h>
using namespace std;

const int maxh = 20;

struct Pos {
  int r, c;
  Pos(int r=0, int c=0) : r(r), c(c) {}
};

int H, W, A, B;
int G[maxh][maxh];

Pos nextPos(int r, int c) {
  r--;
  c--;
  int id = r * W + c;
  id++;
  r = id / W;
  c = id % W;
  return Pos(r+1, c+1);
}

void dfs(Pos pos, int cnta, int cntb, int &ans) {
  int r = pos.r, c = pos.c;
  Pos npos = nextPos(r, c);
  if (cnta == 0 && cntb == 0) {
    ans++;
    return;
  }

  if (G[r][c] > 0) {
    dfs(npos, cnta, cntb, ans);
    return;
  }

  // PUSH B
  if (cntb > 0) {
    G[r][c] = 1;
    dfs(npos, cnta, cntb-1, ans);
    G[r][c] = 0;
  }

  if (cnta > 0) {
    // PUSH A with horizontally
    if (c+1 <= W && !G[r][c+1]) {
      G[r][c] = G[r][c+1] = 2;
      dfs(npos, cnta-1, cntb, ans);
      G[r][c] = G[r][c+1] = 0;
    }

    // PUSH A with vertically
    if (r+1 <= H && !G[r+1][c]) {
      G[r][c] = G[r+1][c] = 2;
      dfs(npos, cnta-1, cntb, ans);
      G[r][c] = G[r+1][c] = 0;
    }
  }

}

int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  // freopen("in", "r", stdin);

  cin >> H >> W >> A >> B;
  int ans = 0;
  dfs(Pos(1, 1), A, B, ans);
  cout << ans;
  return 0;
}
