#pragma GCC optimize("O3")
// #include <atcoder/all>
// using namespace atcoder;
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// gp_hash_table<int, int> mapka;

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

// using mint = modint998244353;
// ostream& operator<<(ostream& out, mint m){
//   out << m.val();
//   return out;
// }

const int P = 998244353;
void add(int &a,int b){
  a += b;
  if(a >= P)
    a -= P;
}
void sub(int &a,int b){
  a -= b;
  if(a < 0)
    a += P;
}
int mul(int a,int b){
  return a * b % P;
}
int n;
int res = 0;
vector<vector<int>> dp;
vector<int> t;
void add(int x){
  int pom = t[x];
  int a = SZ(dp);
  int b = SZ(dp[0]);
  vector<vector<int>> dp2(a + 1,vector<int>(b + pom));
  R(i,a)R(j,b){
    add(dp2[i + 1][j + pom], mul(dp[i][j], i + 1));
    if(j <= pom){
      add(dp2[a - i][pom - j], mul(dp[i][j], a - i));
    }else{
      add(dp2[i][j - pom], mul(dp[i][j], a - i));
    }
  }
//   debug(dp,pom,dp2);
  swap(dp,dp2);
}
void licz(int po,int ko){
  if(po + 1 == ko){
    debug(po,dp);
    R(i,SZ(dp)){
      R(j,min(SZ(dp[0]), t[po])){
        sub(res, dp[i][j]);
      }
    }
    debug(po,t[po],res);
    return;
  }
  int m = (po + ko) / 2;
  auto pam = dp;
  for(int i = po; i < m; i++)add(i);
  licz(m,ko);
  swap(dp,pam);
  for(int i = m; i < ko; i++)add(i);
  licz(po,m);
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  cin >> n;
  t.resize(n);
  res = 1;
  R(i,n){
    cin >> t[i];
    res = mul(res, i + 1);
  }
  debug(res);
  dp.resize(1,vector<int>(1,1));
  licz(0,n);
  cout << res << "\n";
}

#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0, length = n; i < length; i++)
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ep emplace
#define epb emplace_back
#define scll static_cast<long long> 
#define sz(x) static_cast<int>((x).size())
#define pfll(x) printf("%lld\n", x)
#define ci(x) cin >> x
#define ci2(x, y) cin >> x >> y
#define ci3(x, y, z) cin >> x >> y >> z
#define ci4(w, x, y, z) cin >> w >> x >> y >> z
#define co(x) cout << x << endl
#define co2(x, y) cout << x << " " << y << endl
#define co3(x, y, z) cout << x << " " << y << " " << z << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef priority_queue<int> PQ;
typedef priority_queue<int, vector<int>, greater<int>> PQG;
typedef priority_queue<P> PQP;
typedef priority_queue<P, vector<P>, greater<P>> PQPG;

const int MAX_N = 2e5, MOD = 1e9 + 7, INF = 1e9;
int n, m, k;
vector<int> to[100];
typedef vector<int> vec;
typedef vector<vec> mat;

int po(int x, int y) {
    int ans = 1;
    while (y > 0) {
        if (y & 1) ans = static_cast<long>(ans) * x % MOD;
        x = static_cast<long>(x) * x % MOD;
        y >>= 1;
    }
    return ans;
}

mat mul(mat &A, mat &B) {
    mat C(A.size(), vec(B[0].size()));
    for (int i = 0; i < A.size(); i++) {
        for (int k = 0; k < B.size(); k++) {
            for (int j = 0; j < B[0].size(); j++) {
                C[i][j] = (C[i][j] + scll(A[i][k]) * B[k][j] % MOD) % MOD;
            }
        }
    }
    return C;
}

mat pow(mat A, long n) {
    mat B(A.size(), vec(A.size()));
    for (int i = 0; i < A.size(); i++) {
        B[i][i] = 1;
    }
    while (n > 0) {
        if (n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

int main() {
    ci3(n, m, k);
    mat a(n, vec(1));
    rep(i, n) ci(a[i][0]);
    rep(i, m) {
        int x, y;
        ci2(x, y);
        to[x - 1].epb(y - 1);
        to[y - 1].epb(x - 1);
    }
    mat PRO(n, vec(n));
    rep(i, n) {
        rep(j, n) PRO[i][j] = 0;
        for (auto &j: to[i]) PRO[i][j] = 1;
        PRO[i][i] = (2 * m - to[i].size()) % MOD;
    }
    mat POPRO = pow(PRO, k);
    mat ans = mul(POPRO, a);
    int pp = po(po(2 * m, MOD - 2), k);
    rep(i, n) co(scll(ans[i][0]) * pp % MOD);
    return 0;
}
