問題文

$2$ 次元トーラスの海に $A\times B$ 頭のくじらが集まってきました。

トーラス上の座標を $(x,y)$ で表します。$2$ つの座標 $(x_1,y_1),\ (x_2,y_2)$ は、$x_1-x_2,y_1-y_2$ がそれぞれ $A,B$ の整数倍であるとき、またそのときに限り同じ座標とみなします。

時刻 $t=0$ において, $0\le x\lt A, 0\le y\lt B$ を満たすすべての整数組 $(x,y)$ に対して、 座標 $(x,y)$ に $1$ 頭のくじらが停まっています。

どのくじらも泳ぎながら眠りたいですが、衝突が起こらないように安全な計画を立てなければいけません。

各くじらの泳ぐ方向を次の $4$ 通りのいずれかに割り当てます。方向と泳ぎ方の対応は次のとおりです。 ただし、任意の正の実数 $t$ に対して成り立ちます。

$t=0$ にくじらたちが一斉に泳ぎ始めたのち、$10^{100}$ 秒以内に一度も衝突が起きてはいけません。 ただし、衝突が起こるとは、同時刻に同じ座標に異なるくじらが移動することを指します。

$A\times B$ 頭のくじらのうち、$K$ 頭のくじらの方向は既に決まっています。そのうち $i$ 番目のくじらは $(x_i,y_i)$ に停まっており、方向は $d_i$ です。 残りの $A\times B-K$ 頭のくじらを $4$ 方向のいずれかに割り当てる方法の数を $998244353$ で割ったあまりを求めてください。

$1$ つの入力につき、$T$ ケースについてそれぞれ解いてください。

制約

入力

入力は以下の形式で標準入力から与えられる。ここで、$\mathrm{test}_i$ は $i$ 番目のテストケースを意味する。

$T$
$\mathrm{test}_1$
$\mathrm{test}_2$
$\quad\vdots$
$\mathrm{test}_T$

各テストケースは以下の形式で与えられる。

$A$ $B$ $K$
$x_1$ $y_1$ $d_1$
$x_2$ $y_2$ $d_2$
$\qquad\vdots$
$x_K$ $y_K$ $d_K$

出力

方向が決まっていない $A\times B-K$ 頭のくじらを $4$ 方向のいずれかに割り当てる方法の数を $998244353$ で割ったあまりを求めてください。

$1$ テストケースごとに改行してください。

サンプル

4
2 1 0
2 2 3
0 0 U
1 0 L
1 1 D
100 100 2
0 0 U
0 99 D
314 159 2
65 35 L
89 79 R

6
2
0
417706019