第二類史特靈數（Stirling numbers of the second kind）是將 $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}$ 為多少。

輸入格式

第一行輸入三個整數 $n, m, k$，意義如題目描述所示。

接下來 $k$ 行每行輸入三個數 $x_i, y_i, z_i$，表示 $f(x_i, y_i)$ 在計算完成後實際寫入的值為 $z_i$。

輸出格式

輸出一個整數，表示計算得到的實際 $f(n, m)$ 結果。

範例

輸入格式 1

5 3 1
1 0 1

輸出格式 1

31

輸入格式 2

1000 100 0

輸出格式 2

958221900

輸入格式 3

見選手目錄下的 broken/broken3.in 與 broken/broken3.ans。

子任務

對於 100% 的資料，保證 $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})$。