小 D 有 n 个木桶,每个木桶由 m 块类型互不相同的木板构成。对于一个木桶,如果它的木板长度为 a1,a2,...,am,那么这个木桶所能盛放的液体体积为 min。
小 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