題目背景

憶哀（Yi Ai）は、第二類スターリング数の計算方法を学んだばかりです。彼女は、この数学的な概念をプログラミングで実装することに挑戦しました。しかし、彼女のコンピュータは非常に古く、メモリに深刻な問題が発生しています。彼女が書いたプログラムが正しく動作するように、メモリの破損を考慮した計算結果を求める手助けをしてあげてください。

問題文

第二類スターリング数とは、$n$ 個の要素を $m$ 個の空でない集合に分割する組み合わせの数であり、これを $f(n, m)$ と表記します。

憶哀のプログラムは、以下の非常に単純な漸化式を用いています。 $f(n, m) = f(n - 1, m - 1) + m f(n - 1, m)$ 初期値は $f(0, 0) = 1, f(0, m) = 0 (m \neq 0)$ です。この漸化式の意味は説明が容易です。第 $n$ 要素が単独で集合を成すか、あるいは既存の $m$ 個の集合のいずれかに割り当てられるかのいずれかであるためです。

憶哀のプログラムは以下の通りです。

for (int i = 1; i <= n; ++i)
for (int j = 0; j <= min(i, m); ++j)
f[i][j] = (f[i - 1][j - 1] +
j * (long long)f[i - 1][j]) % 998244353;

（配列の範囲外は 0 と見なすことができ、コンピュータ上では $(n + 1) \times (m + 1)$ の配列が確保されていると考えてください）

本来、憶哀のプログラムは $f(n, m) \pmod{998244353}$ を出力するはずでしたが、問題が発生しました。何らかの理由により、$f(x, y)$ を計算した直後にメモリへの書き込みで予期せぬ事態が発生し、メモリ上の $f(x, y)$ が値 $z$ に書き換えられてしまいました。このような事象は、異なる $(x, y)$ に対して合計 $k$ 回発生しました。

これら $k$ 回の予期せぬ書き換えが発生した後の、実際に憶哀のプログラムが出力する $f(n, m) \pmod{998244353}$ の値を求めてください。

入力

1 行目に 3 つの整数 $n, m, k$ が与えられます。意味は問題文の通りです。 続く $k$ 行の各行には 3 つの整数 $x_i, y_i, z_i$ が与えられ、$f(x_i, y_i)$ の計算完了後に実際に書き込まれた値が $z_i$ であることを示します。

出力

計算された実際の $f(n, m)$ の結果を 1 つの整数として出力してください。

入出力例

入出力例 1

5 3 1
1 0 1

31

入出力例 2

1000 100 0

958221900

入出力例 3

選手ディレクトリ内の broken/broken3.in および broken/broken3.ans を参照してください。

すべてのデータにおいて、以下が保証されます。 $1 \le x_i \le n \le 9 \times 10^8$ $0 \le y_i \le m \le \min(n, 10^5)$ $0 \le k \le 20$ $0 \le y_i \le x_i$ $0 \le z_i < 998244353$ $(x_i < x_{i+1}) \lor (x_i = x_{i+1} \land y_i < y_{i+1})$