#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100 + 5;
const ll mod = 1e9 + 7;
int n, m, k, b[maxn][maxn];
ll powMod(ll a, ll k) { ll ret = 1; while(k) { if(k & 1) ret = ret * a % mod; a = a * a % mod; k >>= 1;} return ret;}
ll getinv(ll x) { return powMod(x, mod - 2);}
struct Mat
{
	int r, c;
	ll a[maxn][maxn];
	Mat (const int & _r, const int & _c) : r(_r), c(_c) { memset(a, 0, sizeof a);}
	void setone()
	{
		assert(r == c);
		memset(a, 0, sizeof a);
		for(int i = 0; i < r; ++i) a[i][i] = 1;
	}		
	Mat operator * (const Mat & rhs) const
	{
		Mat ret(r, rhs.c);
		for(int i = 0; i < r; ++i)
			for(int j = 0; j < c; ++j)
			{
				ll tmp = a[i][j];
				for(int k = 0; k < rhs.c; ++k)
					ret.a[i][k] = (ret.a[i][k] + tmp * rhs.a[j][k] % mod) % mod;
			}
		return ret;
	}
};
Mat powMod(Mat a, ll k)
{
	assert(a.r == a.c);
	Mat ret(a.r, a.r);
	ret.setone();
	while(k)
	{
		if(k & 1) ret = ret * a;
		a = a * a; k >>= 1;
	}
	return ret;
}		
int main()
{
	scanf("%d%d%d", &n, &m, &k);
	const ll inv2m = getinv(2 * m);
	Mat v(n, 1);
	for(int i = 0; i < n; ++i) scanf("%lld", &v.a[i][0]);
	for(int i = 0; i < m; ++i)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		--u, --v;
		++b[u][v];
		++b[v][u];
	}
	Mat A(n, n);
	A.setone();
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < n; ++j)
		{
			if(i == j) continue;
			A.a[i][j] = b[i][j] * inv2m % mod;
			A.a[i][i] = (A.a[i][i] + mod - A.a[i][j]) % mod;
		}
	v = powMod(A, k) * v;
	for(int i = 0; i < n; ++i) printf("%lld\n", v.a[i][0]);
	return 0;
}
#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<set>
using namespace std;

#define NDEBUG
#include<cassert>

namespace Elaina{
    #define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
    #define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
    #define fi first
    #define se second
    #define mp(a, b) make_pair(a, b)
    #define Endl putchar('\n')
    #define mmset(a, b) memset(a, b, sizeof a)
    #define siz(a) ((int)(a).size())
    typedef long long ll;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    template<class T>inline T fab(T x){ return x<0? -x: x; }
    template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); }
    template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); }
    template<class T>inline T readin(T x){
        x=0; int f=0; char c;
        while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
        for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
        return f? -x: x;
    }
    template<class T>inline void writc(T x, char s='\n'){
        static int fwri_sta[1005], fwri_ed=0;
        if(x<0) putchar('-'), x=-x;
        do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
        while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
        putchar(s);
    }
}
using namespace Elaina;

const int maxm=2e5;

pii pawn[maxm+5];

int n, m;

inline void input(){
    n=readin(1), m=readin(1);
    rep(i, 1, m)
        pawn[i].fi=readin(1), pawn[i].se=readin(1);
    sort(pawn+1, pawn+m+1);
}

set<int>avai;
vector<int>rem, ins;
inline int saya(int x){
    auto it=avai.find(x);
    if(it!=avai.end() && (*it)==x) return 1;
    return 0;
}

signed main()
{
    input();
    avai.insert(n);
    for(int l=1, r; l<=m; l=r+1){
        for(r=l; r<=m && pawn[r+1].fi==pawn[l].fi; ++r);
        rep(i, l, r) rem.push_back(pawn[i].se);
        rep(i, l, r){
            if(saya(pawn[i].se-1) || saya(pawn[i].se+1))
                ins.push_back(pawn[i].se);
        }
        while(!rem.empty()) avai.erase(rem.back()), rem.pop_back();
        while(!ins.empty()) avai.insert(ins.back()), ins.pop_back();
    }
    writc(siz(avai));
    return 0;
}