#include <bits/stdc++.h>
using namespace std;

using ll = long long;

// 組合せを素数で割った値
const int MAX = 510000;
const ll MOD = 1e9 + 7;
ll fac[MAX], finv[MAX], inv[MAX];

// 前処理
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++) {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

// 二項係数計算
ll COM(int n, int r) {
  if (n < r || n < 0 || r < 0) return 0;
  return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

// 繰り返し自乗法(x^nをmで割った余り) O(logn)
ll power(ll x, ll n, ll m) {
  ll res = 1;
  if (n > 0) {
    res = power(x, n / 2, m);
    if (n % 2 == 0) res = (res * res) % m;
    else res = ((res * res % m) * x) % m;
  }
  return res;
}

// A*B(行列の掛け算, 各項はmで割った余り)
vector<vector<ll>> mul(const vector<vector<ll>> &A, const vector<vector<ll>> &B, ll m) {
  vector<vector<ll>> C(A.size(), vector<ll>(B[0].size(), 0));
  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] + A[i][k] * B[k][j]) % m;
      }
    }
  }
  return C;
}

// A^n(行列累乗, 各項はmで割った余り)
vector<vector<ll>> power_M(vector<vector<ll>> A, ll n, ll m) {
  vector<vector<ll>> B(A.size(), vector<ll>(A.size(), 0));
  for (int i = 0; i < A.size(); i++) B[i][i] = 1;
  
  while (n > 0) {
    if (n & 1) B = mul(B, A, m);
    A = mul(A, A, m);
    n >>= 1;
  }
  return B;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  COMinit();
  
  ll n, m, kk;
  cin >> n >> m >> kk;
  
  vector<ll> a(n);
  for (int i = 0; i < n; i++) cin >> a.at(i);
  
  vector<ll> x(m), y(m);
  for (int i = 0; i < m; i++) {
    cin >> x[i] >> y[i];
    x[i]--;
    y[i]--;
  }
  
  ll inv_2 = power(2, MOD - 2, MOD);
  
  vector<vector<ll>> M(n, vector<ll>(n, 0));
  for (int k = 0; k < m; k++) {
    M[x[k]][y[k]] += inv_2;
    M[x[k]][y[k]] %= MOD;
    M[x[k]][x[k]] += inv_2;
    M[x[k]][x[k]] %= MOD;
    M[y[k]][x[k]] += inv_2;
    M[y[k]][x[k]] %= MOD;
    M[y[k]][y[k]] += inv_2;
    M[y[k]][y[k]] %= MOD;
    for (int i = 0; i < n; i++) {
      if (i == x[k] || i == y[k]) continue;
      M[i][i] += 1;
      M[i][i] %= MOD;
    }
  }
  
  vector<vector<ll>> M2 = power_M(M, kk, MOD);
  
  ll keep = power(power(m, kk, MOD), MOD - 2, MOD);
  
  vector<ll> ans(n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
//      cout << M2[i][j] << " ";
      ans[i] += M2[i][j] * a[j] % MOD;
      ans[i] %= MOD;
    }
//    cout << endl;
    cout << (ans[i] * keep) % MOD << '\n';
  }
}
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;

typedef long long LL;
typedef pair<int,int> PI;
typedef vector<int> VI;
typedef vector<PI> VPI;

template<class T> bool tmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool tmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
#define F first
#define S second
#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int _n(b),i(a);i<_n;i++) 
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define TRAV(a,x) for (auto& a : x)

void setIO() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
}

const int mod = 998244353;

int madd(int a, int b) {
    a = a + b;
    while (a < 0) a += mod;
    while (a >= mod) a -= mod;
    return a;
}

int mmul(int a, int b) {
    return (a * 1ll * b) % mod;
}

int mpow(int a, int n) {
    int r = 1;
    for(; n; n >>= 1) {
        if (n&1) r = mmul(r, a);
        a = mmul(a, a);
    }
    return r;
}

int minv(int a) {
    return mpow(a, mod-2);
}

int mdiv(int a, int b) {
    return mmul(a, minv(b));
}


const int MX = 5005;
char g[MX][MX];
int n, m, k;
int mem[MX][MX];
int tot, b3;

int f(int i, int j) {
    if (i == n && j == m)
        return tot;
    if (i > n || j > m)
        return 0;

    int &r = mem[i][j];
    if (r != -1) return r;

    if (g[i][j] == 'R')
        r = f(i, j+1);
    else if (g[i][j] == 'D')
        r = f(i+1, j);
    else if (g[i][j] == 'X')
        r = madd(f(i, j+1), f(i+1, j));
    else
        r = mmul(mmul(2, madd(f(i, j+1), f(i+1, j))), b3);

    return r;
}

int solve() {
    tot = mpow(3, n * m - k);
    b3 = minv(3);
    memset(mem, -1, sizeof mem);
    return f(1, 1);
}

int main() {
    setIO();
    int t=1; // cin>>t;
    while(t--) {
        cin>>n>>m>>k;
        REP(i, n+1) REP(j, m+1) g[i][j] = '?';
        REP(l, k) {
            int i, j; cin >> i >> j;
            cin >> g[i][j];
        }
        cout<<solve()<<"\n";
    }
    
    return 0;
}
