#include<bits/stdc++.h>
#define N 105
#define P 1000000007
using namespace std;
int n,m,k,t[N],ni,a[N];
void Add(int &x,int y){
	x+=y;
	if(x>=P)x-=P;
}
int fpow(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=1ll*res*a%P;
		a=1ll*a*a%P,b>>=1;
	}return res;
}
struct S{
	int A[N][N];
	S operator *(const S &_)const{
		S res;
		for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)res.A[i][j]=0;
		for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)for(int k=1;k<=n;++k)res.A[i][j]=(res.A[i][j]+1ll*A[i][k]*_.A[k][j])%P;
		return res;
	}
}ans,I;
bool v[N][N];
int main(){
	cin>>n>>m>>k;ni=fpow(2*m,P-2);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]),ans.A[i][i]=1;
	for(int x,y,i=1;i<=m;++i)scanf("%d%d",&x,&y),v[x][y]=v[y][x]=1,++t[x],++t[y];
	for(int i=1;i<=n;++i){
		I.A[i][i]=1ll*(m*2-t[i]+P)*ni%P;
		for(int j=1;j<=n;j++)if(v[i][j])I.A[i][j]=ni;
	}
	for(int i=0;k;++i,I=I*I){
		if(k&(1<<i))k^=(1<<i),ans=ans*I;
	}for(int i=1;i<=n;i++){
		int res=0;
		for(int j=1;j<=n;j++)res=(res+1ll*a[j]*ans.A[i][j])%P;cout<<res<<"\n";
	}
}
//#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<time.h>
#include<stdio.h>
#include<string.h>
#define un unsigned
#define srd srand(time(0))
#define ll long long
#define con continue
#define gtc getchar()
#define ptc putchar
#define dou double
#define eps 0.00000000001
#define opr operator
#define cl(x,a) memset(x,a,sizeof(x))
#define fo0(i,k) for(i=fr[k];i;i=nx[i])
#define fo1(i,l,r) for(i=l;i<=r;i++)
#define fo2(i,l,r) for(i=l;i>=r;i--)
#define fo(i,n) for(i=1;i<=n;i++)
#define ret return
#define x first
#define cint const int
#define y second
#define opi(x) freopen(x,"r",stdin)
#define opo(x) freopen(x,"w",stdout)
#define tpl template<class T>
#define priq priority_queue
#define mp make_pair
#define use using namespace
#define WT while(T--)
#define pb push_back
#define sz size()
use std;
typedef pair<int,int> pii;typedef pair<int,ll> pil;typedef pair<ll,int> pli;typedef pair<ll,ll> pll;
namespace io
{
	void _(int &k){char c;int e=1;k=0;while((c=gtc)>'9'||c<'0')if(c=='-')e=-1;k=c-'0';while((c=gtc)<='9'&&c>='0'){k*=10;k+=c-'0';}k*=e;}
	void _(ll &k){char c;int e=1;k=0;while((c=gtc)>'9'||c<'0')if(c=='-')e=-1;k=c-'0';while((c=gtc)<='9'&&c>='0'){k*=10;k+=c-'0';}k*=e;}
	void _(char &c){while((c=gtc)==' '||c=='\n');}void _(dou &c){scanf("%lf",&c);}void _(char *s){char c;while((c=gtc)!=EOF&&c!=' '&&c!=10)*s++=c;}
	template<class t1,class t2>void _(t1 &a,t2 &b){_(a);_(b);}template<class t1,class t2,class t3>void _(t1 &a,t2 &b,t3 &c){_(a);_(b);_(c);}
	template<class t1,class t2,class t3,class t4>void _(t1 &a,t2 &b,t3 &c,t4 &d){_(a);_(b);_(c);_(d);}
	template<class t1,class t2,class t3,class t4,class t5>void _(t1 &a,t2 &b,t3 &c,t4 &d,t5 &e){_(a);_(b);_(c);_(d);_(e);}
	void _p(dou k){printf("%.6lf",k);}void _p(char *c){for(;*c;ptc(*c++));}void _p(const char *c){for(;*c;ptc(*c++));}void _p(char c){ptc(c);}
	tpl void _p0(T k){if(k>=10)_p0(k/10);ptc(k%10+'0');}tpl void _p(T k){if(k<0){ptc('-');_p0(-k);}else _p0(k);}tpl void __p(T k){_p(k);ptc(' ');}
	tpl void _pn(T k){_p(k);ptc('\n');}template<class t1,class t2>void _p(t1 a,t2 b){__p(a);_pn(b);}
	template<class t1,class t2,class t3>void _p(t1 a,t2 b,t3 c){__p(a);__p(b);_pn(c);}
	template<class t1,class t2,class t3,class t4>void _p(t1 a,t2 b,t3 c,t4 d){__p(a);__p(b);__p(c);_pn(d);}
	tpl void op(T *a,int n){int i;n--;fo(i,n)__p(a[i]);_pn(a[n+1]);}int gi(){int x;_(x);ret x;}ll gll(){ll x;_(x);ret x;}
}
int gcd(int a,int b){ret b?gcd(b,a%b):a;}void fcl(){fclose(stdin);fclose(stdout);}
void fop(const char *s){char c[256],d[256];cl(c,0);cl(d,0);strcpy(c,s);strcpy(d,s);opi(strcat(c,".in"));opo(strcat(d,".out"));}
int eq(dou a,dou b){return a+eps>=b&&b+eps>=a;}tpl void _ma(T &a,T b){if(a<b)a=b;}tpl void _mi(T &a,T b){if(a>b)a=b;}
cint N=233333,EE=100000000,p=1000000007,ima=2147483647;
use io;
int n,m,c[22][22],f[N][17][17],v[22],po[22][N],sm;
/*int cc(int t,int k)
{
	int rt=0,i;
	if(k>m)
		return 0;
	int d=m-k;
	fo1(i,0,d)
		rt=(rt+(1-(d-i)%2*2)*1ll*po[i+k][t]*c[16-k][i]+(ll)p*p)%p;
	return rt;
}*/
char a[N];
int main()
{
	int i,j,k,a1,a2,an=0;
	scanf(" %s",a+1);
	n=strlen(a+1);
	fo(i,n)
		if(a[i]>='0'&&a[i]<='9')
			a[i]-='0';
		else
			a[i]-='A'-10;
	_(m);
	fo1(i,0,16)
		c[i][0]=1;
	fo(i,16)
		fo(j,16)
			c[i][j]=c[i-1][j]+c[i-1][j-1];
	fo1(i,1,16)
	{
		po[i][0]=1;
		fo(j,n)
			po[i][j]=(ll)po[i][j-1]*i%p;
	}
	fo1(i,0,m)
		f[0][i][i]=1;
	fo(i,n)
		fo(j,m)
			fo1(k,j,m)
				f[i][j][k]=((ll)f[i-1][j][k-1]*(17-k)+(ll)f[i-1][j][k]*k)%p;
	fo(i,n)
		an=(an+15ll*f[i-1][1][m])%p;
	fo(i,n)
	{
		fo1(j,a[i]+1,15)
			an=(an-f[n-i][sm+(!v[j])][m]+p)%p;
		sm+=!v[a[i]];
		v[a[i]]=1;
	}
	_pn(an);
}

