#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define FF first
#define SS second
#define pb push_back
#define mp make_pair

typedef long long int LL;
typedef pair<int, int > pii;
typedef vector<int > vi;

const int mod = 1000000007;
const int N = 101;

LL A[N][N], B[N][N], C[N][N];
int G[N][N];
int X[N];

LL _pow(LL a, LL b) {
  if(!b) return 1;
  if(b == 1) return a;
  if(b == 2) return a * a % mod;
  if(b & 1) {
    return a * _pow(a,b-1) % mod;
  }
  return _pow(_pow(a,b/2),2);
}

int n;
void solve(int k) {
  if(k == 0) {
    memset(B, 0, sizeof(B));
    rep(i,0,n) B[i][i] = 1;
    return;
  }
  solve(k / 2);
  memset(C, 0, sizeof(C));
  rep(i,0,n) {
    rep(j,0,n) {
      rep(k,0,n) {
        C[i][j] += B[i][k] * B[k][j];
        C[i][j] %= mod;
      }
    }
  }
  memcpy(B, C, sizeof(C));

  if(k & 1) {
    memset(C, 0, sizeof(C));
    rep(i,0,n) {
      rep(j,0,n) {
        rep(k,0,n) {
          C[i][j] += B[i][k] * A[k][j];
          C[i][j] %= mod;
        }
      }
    }
    memcpy(B, C, sizeof(C));
  }
}

int main() {
  int m,k;
  scanf("%d%d%d",&n,&m,&k);
  rep(i,0,n) S(X[i]);
  rep(i,0,m) {
    int x,y;
    S2(x,y);
    x--; y--;
    G[x][y] = G[y][x] = 1;
  }
  int inv = _pow(2 * m, mod - 2);
  rep(i,0,n) {
    int cnt = m;
    rep(j,0,n) {
      if(G[i][j]) {
        cnt--;
        A[i][j]++;
        A[i][i]++;
      }
    }
    A[i][i] += 2 * cnt;
    rep(j,0,n) {
      A[i][j] = A[i][j] * inv % mod;
    }
  }

  solve(k);
  rep(i,0,n) {
    LL ans = 0;
    rep(j,0,n) {
      ans += B[i][j] * X[j];
      ans %= mod;
    }
    P((int)ans);
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
char s[200005];
int n,k;
int f[200005][20];
int a[200005];
bool v[20];
const int mod=1e9+7;
void add(int &x,int y){
	x+=y;
	if(x>=mod)x-=mod;
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++){
		if(s[i]>='0'&&s[i]<='9')a[i]=s[i]-'0';
		else a[i]=s[i]-'A'+10;
	}
	f[1][1]=a[1]-1;
	int tot=0;
	for(int i=1;i<n;i++){
		if(!v[a[i]]){
			v[a[i]]=1;
			++tot;
		}
		for(int j=1;j<=min(i,16);j++){
			add(f[i+1][j],1ll*f[i][j]*j%mod);
			if(j<16)add(f[i+1][j+1],1ll*f[i][j]*(16-j)%mod);
		}
		for(int j=0;j<a[i+1];j++){
			if(v[j])add(f[i+1][tot],1);
			else add(f[i+1][tot+1],1);
		}
		add(f[i+1][1],15);
	}
	if(!v[a[n]]){
		v[a[n]]=1;
		tot++;
	}
	cin>>k;
	if(k==tot)add(f[n][k],1);
	cout<<f[n][k];
}