小 D 有 $n$ 个木桶，每个木桶由 $m$ 块类型互不相同的木板构成。对于一个木桶，如果它的木板长度为 $a_1,a_2,...,a_m$，那么这个木桶所能盛放的液体体积为 $\min_{i=1}^m a_i$。

小 D 的 $n$ 个木桶很神奇，它们所能造成的收益并不简单的是每个木桶的液体体积之和，而是每个木桶的液体体积之积。也就是说，对于这 $n$ 个木桶，如果第 $i$ 个木桶的第 $j$ 块木板的高度为 $p_{j,i}$，那么这些木桶造成的收益为 $\prod_{i=1}^n (\min_{j=1}^m p_{j,i})$。

小 D 已经从木材店买到了一些木板，但是，木材店的木板数量是很有限的。具体来说，对于这 $m$ 种木板，每种木板小 D 恰好有 $1\sim n$ 长度的木板各一个。小 D 现在已经放好了 $q$ 条木板，但还没有想好怎么放置这些木板，所以，他希望你能求出来对于所有合法的放置木板的方案对应的收益之和。由于这个数可能很大，所以他只需要你输出对 $998244353$ 取模的结果。

形式化题意

有 $m$ 个长度为 $n$ 的排列，其中共有 $q$ 个位置的值已经确定，其余位置未确定。求所有本质不同的排列组对应的 $\prod_{i=1}^n (\min_{j=1}^m p_{j,i})$ 之和。对 $998244353$ 取模。两组排列 $P,Q$ 本质不同，当且仅当存在 $i,j$ 使得 $P_{i,j} \neq Q_{i,j}$。保证至少存在一种合法方案。

输入格式

第一行三个数 $n,m,q$，含义见题目描述。

接下来 $q$ 行，每行三个数 $x,y,w$，表示要求 $p_{x,y}=w$。

输出格式

一行一个数，表示所有方案的收益之和对 $998244353$ 取模的结果。

样例组

样例 1 输入

2 2 0

样例 1 输出

6

样例 2 输入

3 2 1
1 1 1

样例 2 输出

38

样例 3 输入

50 50 5
6 18 17
10 2 14
43 12 40
11 50 37
45 23 4

样例 3 输出

830538815

数据范围

本题采用捆绑测试。

对于所有的数据，满足 $1\leq n\leq 50,1\leq m < 998244353,0\leq q\leq 10,1\leq x\leq m,1\leq y,w\leq n$。

• Subtask 1(4pts)：$n\leq 5,m\leq 3,q\leq 5$。
• Subtask 2(8pts)：$n\leq 7,m\leq 3,q\leq 5$。
• Subtask 3(8pts)：$m\leq 2,q=0$。
• Subtask 4(12pts)：$q=0$。
• Subtask 5(16pts)：$n\leq 20,q\leq 5$。
• Subtask 6(12pts)：$q\leq 5$。
• Subtask 7(20pts)：$q\leq 7$。
• Subtask 8(12pts)：$q\leq 9$。
• Subtask 9(8pts)：无特殊限制。

时间限制：5s

空间限制：512MB