#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <cstdio>
#include <numeric>
#include <iomanip>

using namespace std;

using ll = long long;

const ll M = 998244353;
ll dp[5001][5001];
char G[5001][5001];
ll H, W, K;

bool bc(ll i, ll j)
{
    return 0 <= i && i < H && 0 <= j && j < W;
}

ll modpow(ll b, ll e, ll m)
{
    ll ret = 1;
    while (e > 0) 
    {
       if ((e & 1) == 1)
       {
           ret = (ret * b) % m; 
       }
       e >>= 1;
       b = (b * b) % m;
    }
    return ret;
}

int main()
{
    cin >> H >> W >> K;
    for(ll i = 0;i < K;i++)
    {
        ll h, w;
        char c;
        cin >> h >> w >> c;
        G[h-1][w-1] = c;
    }
    dp[0][0] = modpow(3, H*W-K, M);
    ll inv3 = modpow(3, M-2, M);
    for(ll i = 0;i < H;i++)
    {
        for(ll j = 0;j < W;j++)
        {
            ll inc = 0;
            if(bc(i-1, j))
            {
                if(G[i-1][j] == 'D' || G[i-1][j] == 'X')
                {
                    inc += dp[i-1][j];
                }
                else if(G[i-1][j] == 0)
                {
                    inc += 2LL * inv3 * dp[i-1][j];
                }
            }
            inc %= M;
            if(bc(i, j-1))
            {
                if(G[i][j-1] == 'R' || G[i][j-1] == 'X')
                {
                    inc += dp[i][j-1];
                }
                else if(G[i][j-1] == 0)
                {
                    inc += 2LL * inv3 * dp[i][j-1];
                }
            }
            dp[i][j] += inc;
            dp[i][j] %= M;
        }
    }
    cout << dp[H-1][W-1] << endl;
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
static const ll mod=1000000007;
using P=pair<ll,ll>;
using mat=vector<vector<ll>>;
ll modpow(ll a,ll n){
ll res=1;
  while(0<n){
  if(n&1)res=(res*a)%mod;
    a=(a*a)%mod;n>>=1;
  }return res;
}
mat mul(const mat &A,const mat &B){
ll H=A.size();ll W=B[0].size();
  mat C(H,vector<ll>(W,0));
  for(ll i=0;i<H;i++)
    for(ll j=0;j<W;j++){
    ll sum=0;
      for(ll k=0;k<B.size();k++)sum=(sum+A[i][k]*B[k][j])%mod;
      C[i][j]=sum;
    }return C;
}
mat matpow(mat A,ll n){
ll H=A.size();
  mat res(H,vector<ll>(H,0));
  for(ll i=0;i<H;i++)res[i][i]=1;
  while(0<n){
  if(n&1)res=mul(res,A);
    A=mul(A,A);n>>=1;
  }return res;
}
ll N,M,K;
int main(){
  cin>>N>>M>>K;vector<ll>a(N);
  for(ll i=0;i<N;i++)cin>>a[i];
  mat A(N,vector<ll>(N,0));
  for(ll i=0;i<N;i++)A[i][i]=1;
  for(ll i=0;i<M;i++){
  ll x,y;cin>>x>>y;x--;y--;
    A[x][y]=(A[x][y]+modpow(2*M,mod-2))%mod;
    A[y][x]=(A[y][x]+modpow(2*M,mod-2))%mod;
    A[x][x]=(A[x][x]+mod-modpow(2*M,mod-2))%mod;
    A[y][y]=(A[y][y]+mod-modpow(2*M,mod-2))%mod;
  }mat C=matpow(A,K);vector<ll>ans(N);
  for(ll i=0;i<N;i++){
  for(ll j=0;j<N;j++)ans[i]=(ans[i]+C[i][j]*a[j])%mod;
  }for(ll i=0;i<N;i++)cout<<ans[i]<<endl;
  
 return 0;
}
