题目背景

构成组织的各个部分往往是优劣不齐的，而劣势部分往往决定整个组织的水平。

题目描述

小 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$ 取模的结果。

2 2 0

6

3 2 1
1 1 1

38

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

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$。

• Subtask 2(8pts)：$n\leq 7,m\leq 3$。

• 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)：无特殊限制。