#include <bits/stdc++.h>          
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repp(i, st, en) for (ll i = (ll)st; i < (ll)(en); i++)
#define repm(i, st, en) for (ll i = (ll)st; i >= (ll)(en); i--)
#define all(v) v.begin(), v.end()
void chmax(ll &x, ll y) {x = max(x,y);}
void chmin(ll &x, ll y) {x = min(x,y);}
void Yes() {cout << "Yes" << endl; exit(0);}
void No() {cout << "No" << endl; exit(0);}
template<class in_Cout> void Cout(in_Cout x) {cout << x << endl; exit(0);}
template<class in_vec_cout>
void vec_cout(vector<in_vec_cout> vec) {
    for (in_vec_cout res : vec) {cout << res << " ";}
    cout << endl;
}

const ll inf = 1e18;
const ll mod = 1e9 + 7;

using mat = vector<vector<ll>>;

ll N, M, K;
bool G[110][110];
mat A, E;

ll powmodp(ll x, ll n) {
    if (n==0) return 1;
    if (n%2) return x * powmodp(x,n-1) % mod;
    ll res = powmodp(x,n/2);
    return res * res % mod;
}

ll inv(ll x) {return powmodp(x,mod-2);}

mat prod(mat x, mat y) {
    ll n = x.size();
    mat res(n,vector<ll>(N));
    rep(i,n) rep(j,N) rep(k,N) {
        res[i][j] += x[i][k]*y[k][j]%mod;
        res[i][j] %= mod;
    }
    return res;
}

mat powmat(mat x, ll n) {
    if (n==0) return E;
    if (n%2) return prod(x,powmat(x,n-1));
    mat res = powmat(x,n/2);
    return prod(res,res);
}

int main() {
    cin >> N >> M >> K;
    A.resize(1,vector<ll>(N));
    rep(i,N) cin >> A[0][i];
    rep(i,M) {
        ll x, y; cin >> x >> y;
        x--; y--;
        G[x][y] = G[y][x] = true;
    }
    E.resize(N,vector<ll>(N));
    rep(i,N) E[i][i] = 1LL;

    ll p = inv(M);
    ll half = inv(2);

    mat f(N,vector<ll>(N));
    rep(j,N) {
        ll cnt = 0;
        rep(i,N) if (G[i][j]) cnt++;
        rep(i,N) {
            if (i==j) {
                ll q = cnt * p % mod;
                ll sub = q * half % mod;
                f[i][j] = (1 + mod - sub) % mod;
            } else if (G[i][j]) {
                f[i][j] = p * half % mod;
            }
        }
    }

    mat F = powmat(f,K);
    mat vec = prod(A,F);

    vector<ll> res = vec[0];
    for (ll ans : res) cout << ans << endl;
}
#define _USE_MA_DEFINES
#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
#include <random>
#include <cassert>
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using namespace std;
#define int long long
#define CONTAINS_VEC(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define REPE(i, n) for (int (i)=0; (i) <= (n); (i)++)
#define CONTAINS_MAP(m, a) ((m).find((a)) != m.end())
#define CONTAINS_SET(m, a) ((m).find((a)) != m.end())
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; exit(0); }
void Yes() { cout << "Yes" << endl; exit(0); }
void No() { cout << "No" << endl; exit(0); }



//----------BIT木 0-index----------
const int BIT_N = 1000010;
int bit_tree[BIT_N];
//[index]にnを追加
void bit_add(int index, int n)
{
	for (int x = index; x < BIT_N; x |= x + 1)
	{
		bit_tree[x] += n;
	}
}
//[0, index)の合計
int bit_sum(int index)
{
	int ret = 0;
	for (int x = index - 1; x >= 0; x = (x & (x + 1)) - 1)
	{
		ret += bit_tree[x];
	}
	return ret;
}


int H, W, M;
int X[200001];
int Y[200001];
vector<int> l_list[200001];
vector<int> __list[200001];

vector<int> m;
bool bit_flg[200001];

signed main()
{
	cin >> H >> W >> M;
	REP(i, M)
	{
		cin >> Y[i] >> X[i];
		X[i]--;
		Y[i]--;

	}

	REP(i, W) l_list[i].push_back(H);
	REP(i, H) __list[i].push_back(W);

	REP(i, M)
	{
		l_list[X[i]].push_back(Y[i]);
		__list[Y[i]].push_back(X[i]);
	}

	REP(i, W)
	{
		SORT(l_list[i]);
	}
	REP(i, H)
	{
		SORT(__list[i]);
	}

	int l_sum = 0;
	int __sum = 0;

	REP(i, W)
	{
		if (l_list[i][0] == 0)
		{
			break;
		}
		l_sum += l_list[i][0];
	}
	REP(i, H)
	{
		if (__list[i][0] == 0)
		{
			break;
		}
		__sum += __list[i][0];
	}

	for (int i = 0; i < W; i++)
	{
		bit_flg[i] = true;
		bit_add(i, 1);
	}

	int x_sum = 0;
	for (int y = 0; y < l_list[0][0]; y++)
	{
		for (auto p : __list[y])
		{
			if (bit_flg[p])
			{
				bit_add(p, -1);
				bit_flg[p] = false;
			}
		}

		x_sum += bit_sum(min(__list[y][0], __list[0][0]));
	}

	cout << l_sum + __sum - x_sum;

}

