#include <bits/stdc++.h>          
using namespace std;
using ll = long long;
using ld = long double;
using matrix = vector<vector<ll>>;
#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()
template<class in_chmax> void chmax(in_chmax &x, in_chmax y) {x = max(x,y);}
template<class in_chmin> void chmin(in_chmin &x, in_chmin 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;
const ll maxN = 110;

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);}

matrix E(ll n) {
    matrix res(n,vector<ll>(n));
    rep(i,n) res[i][i] = 1;
    return res;
}

void addmodp(ll &x, ll y) {x = (x + y) % mod;}

matrix prodmatrix(matrix x, matrix y) {
    ll H = x.size(), W = y[0].size(), sz = y.size();
    matrix res(H,vector<ll>(W));
    rep(i,H) rep(j,W) rep(k,sz) {
        addmodp(res[i][j], x[i][k] * y[k][j] % mod);
    }
    return res;
}
vector<ll> prodmatrix(matrix A, vector<ll> x) {
    matrix X(x.size(),vector<ll>(1));//         |y1|   |A11    |   |x1|
    rep(i,x.size()) X[i][0] = x[i];  //         |y2| = |  A22  | * |x2|
    matrix Y = prodmatrix(A,X);      //         |y3|   |    A33|   |x3|
    vector<ll> y(Y.size());
    rep(i,Y.size()) y[i] = Y[i][0];
    return y;
}
vector<ll> prodmatrix(vector<ll> x, matrix A) {
    matrix X(1,vector<ll>(x.size()));//                               |A11    |
    rep(i,x.size()) X[0][i] = x[i];  // |y1, y2, y3| = |x1, x2, x3| * |  A22  |
    matrix Y = prodmatrix(X,A);      //                               |    A33|
    vector<ll> y(Y[0].size());
    rep(i,Y[0].size()) y[i] = Y[0][i];
    return y;
}

matrix powmatrix(matrix x, ll n) {
    if (n==0) return E(x.size());
    if (n%2) return prodmatrix(x,powmatrix(x,n-1));
    matrix res = powmatrix(x,n/2);
    return prodmatrix(res,res);
}

ll N, M, K;
vector<ll> A(maxN);
matrix mat(maxN,vector<ll>(maxN));
vector<ll> G[maxN];

int main() {
    cin >> N >> M >> K;
    rep(i,N) cin >> A[i];
    rep(i,M) {
        ll x, y; cin >> x >> y;
        x--; y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    rep(now,N) {
        ll n = G[now].size();
        ll p = n * inv(M) % mod, q = (1-p+mod) % mod;
        mat[now][now] = ((p * inv(2) % mod) + q) % mod;
        for (ll to : G[now]) {
            mat[now][to] = inv(M) * inv(2) % mod;
        }
    }
    vector<ll> res = prodmatrix(A,powmatrix(mat,K));
    rep(i,N) cout << res[i] << endl;
}
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define REPR(i,n) for (ll i = (n)-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = (m); i < (n); ++i)
#define FORR(i,m,n) for (ll i = (n)-1; i >= (m); --i)
#define FORE(x,xs) for (const auto& x : (xs))
#define FORI(i,v) for (auto i = v.begin(); i != v.end(); i++)
#define STATE(s,n) for (int s = 0; s < (1 << (n)); s++)
#define SUB(t,s) for (int t = (s); --t&=(s);)
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(ALL(v))
#define REV(v) reverse(ALL(v))
#define UNIQ(v) sort(ALL(v)); v.erase(unique(ALL(v)),end(v))
#define CHMIN(x,y) x = min(x, (y))
#define CHMAX(x,y) x = max(x, (y))
#define BIT(x,i) (((x) >> (i)) & 1)
#define YES(b) cout << ((b) ? "YES" : "NO") << endl
#define Yes(b) cout << ((b) ? "Yes" : "No") << endl
#define RETURN(x) cout << (x) << endl; return

const ll MAX = 1<<20;

ll A, B;
vi PRIMES({2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71});

ll dp[77][MAX];

ll solve() {
    dp[0][0] = 1;
    FOR (i, A, B+1) {
        ll factor = 0;
        REP (ip, 20) if (i%PRIMES[ip] == 0) {
            factor |= (1 << ip);
        }
        REP (k, MAX) {
            dp[i-A+1][k] += dp[i-A][k];
            if ((k&factor) == factor) dp[i-A+1][k] += dp[i-A][k^factor];
        }
    }
    ll ans = 0;
    REP (k, MAX) {
        ans += dp[B-A+1][k];
    }
    return ans;
}

int main() {
    cout << fixed << setprecision(15);
    cin >> A >> B;
    cout << solve() << endl;
}