#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int a[105];
long long E[105][105],A[105][105],B[105][105],C[105][105];
long long qpow(long long x,int n){
	long long ans=1;
	for(;n;n>>=1,x=x*x%mod)if(n&1)ans=ans*x%mod;
	return ans;
}
void mul(long long a[105][105],int n){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			C[i][j]=0;
			for(int k=1;k<=n;k++)C[i][j]=(C[i][j]+a[i][k]*a[k][j])%mod;
		}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=C[i][j];
}
void mul(long long a[105][105],long long b[105][105],int n){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			C[i][j]=0;
			for(int k=1;k<=n;k++)C[i][j]=(C[i][j]+a[i][k]*b[k][j])%mod;
		}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=C[i][j];
}
void Mqpow(int n,int k){
	for(int i=1;i<=n;i++)A[i][i]=1;
	for(;k;k>>=1,mul(E,n))if(k&1)mul(A,E,n);
}
int main(){
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)E[i][i]=1;
	int I=qpow(m,mod-2),I2=qpow(2*m,mod-2);
	for(int i=0;i<m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		E[u][u]=(E[u][u]-I2+mod)%mod;
		E[v][v]=(E[v][v]-I2+mod)%mod;
		E[u][v]=(E[u][v]+I2)%mod;
		E[v][u]=(E[v][u]+I2)%mod;
	}
	Mqpow(n,k);
	for(int i=1;i<=n;i++){
		long long ans=0;
		for(int j=1;j<=n;j++)ans=(ans+A[i][j]*a[j])%mod;
		printf("%lld\n",ans);
	}
}
#include<bits/stdc++.h>
// #pragma optimize("-O3")
//  #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,avx,mmx,tune=native")
using namespace std;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define INF 1e9
//#define BIG_INF 1e18
#define vi vector<ll>
#define sz(a) ll((a).size())
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1)
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
// typedef tree<
// ll,
// null_type,
// less<ll>,
// rb_tree_tag,
// tree_order_statistics_node_update>
// ordered_set;
typedef long long ll;
 const ll BIG_INF = 3e18;
ll mod = 1e9+7;
 ll fast_exp(ll a, ll b)
{
    if(b <= 0)
       return 1;
    else
    {
       ll res = 1;
       res = fast_exp(a,b/2);
       res = (res*res)%mod;
       if(b%2 == 1)
          res = (res*a)%mod;
       return res;
 
    }
}

typedef long double ld;
const long long N = 1e5+1000;
const long double pi = acos(-1.0);
using cd = complex<double>;
const double PI = acos(-1);

int par[2][N] = {};
int comp[2] = {};

int find_par(int v, int mode)
{
    if(par[mode][v] == v)
        return v;
    else 
        return par[mode][v] = find_par(par[mode][v],mode);
}

void union_find(int a, int b, int mode)
{
    a = find_par(a,mode);
    b = find_par(b,mode);
    if(a != b)
    {
        par[mode][a] = b;
        comp[mode]--;
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("input.txt","r",stdin);
    int h, w;
    cin >> h >> w;
    char a[h][w] = {};
    for(int i = 0; i<h; i++)
        for(int j = 0; j<w; j++)
        {
            cin >> a[i][j];
        }
        a[0][0] = '#';
        a[h-1][0] = '#';
        a[0][w-1] = '#';
        a[h-1][w-1] = '#';
    for(int i = 0; i<h; i++)
        par[0][i] = i;
    comp[0] = h;
    for(int i = 0; i<w; i++)
        par[1][i] = i;
    comp[1] = w;

    for(int category = 0; category < w; category++)
    {
        int prev = -1;
        for(int i = 0; i<h; i++)
        {
            if(a[i][category] == '#')
            {
                if(prev == -1)
                    prev = i;
                else
                {
                    union_find(prev,i,0);
                    prev = i;
                }
            }
        }
    }

    for(int category = 0; category < h; category++)
    {
        int prev = -1;
        for(int i = 0; i<w; i++)
        {
            if(a[category][i] == '#')
            {
                if(prev == -1)
                    prev = i;
                else
                {
                    union_find(prev,i,1);
                    prev = i;
                }
            }

        }
    }

    int ans = min(comp[0],comp[1]);
    ans--;
    cout << ans << '\n';




    // cerr<< '\n' << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n" ;
    return 0;
    
    
}










 