Background

The parts that make up an organization are often uneven in quality, and the weaker parts often determine the overall level of the whole organization.

Problem Description

Little D has $n$ barrels. Each barrel is made of $m$ wooden planks, and the $m$ planks are all of different types. For a barrel, if the plank lengths are $a_1,a_2,\ldots,a_m$, then the volume of liquid it can hold is $\min_{i=1}^m a_i$. Little D’s $n$ barrels are magical: the profit they produce is not simply the sum of the liquid volumes of each barrel, but the product of the liquid volumes of all barrels. That is, for these $n$ barrels, if the height of the $j$-th plank of the $i$-th barrel is $p_{j,i}$, then the profit produced by these barrels is $\prod_{i=1}^n (\min_{j=1}^m p_{j,i})$.

Little D has already bought some planks from the lumber store, but the number of planks in the store is limited. Specifically, for each of the $m$ types of planks, Little D has exactly one plank of each length from $1$ to $n$. Little D has now placed $q$ planks, but he has not decided how to place the remaining planks. Therefore, he wants you to compute the sum of profits over all valid placement schemes. Since this number can be very large, you only need to output the result modulo $998244353$.

Formal Statement

There are $m$ permutations of length $n$. Among them, the values at $q$ positions have been fixed, and the remaining positions are unfixed. Find the sum, over all essentially different permutation groups, of $\prod_{i=1}^n (\min_{j=1}^m p_{j,i})$, modulo $998244353$. Two permutation groups $P$ and $Q$ are essentially different if and only if there exist $i,j$ such that $P_{i,j}\neq Q_{i,j}$. It is guaranteed that at least one valid scheme exists.

Input Format

The first line contains three integers $n,m,q$, with meanings as described above.

The next $q$ lines each contain three integers $x,y,w$, meaning that $p_{x,y}=w$ is required.

Output Format

Output one integer, the sum of contributions of all schemes modulo $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

Hint

This problem uses bundled tests.

For all testdata, $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 (4 pts): $n\leq 5,m\leq 3$.
• Subtask 2 (8 pts): $n\leq 7,m\leq 3$.
• Subtask 3 (8 pts): $m\leq 2,q=0$.
• Subtask 4 (12 pts): $q=0$.
• Subtask 5 (16 pts): $n\leq 20,q\leq 5$.
• Subtask 6 (12 pts): $q\leq 5$.
• Subtask 7 (20 pts): $q\leq 7$.
• Subtask 8 (12 pts): $q\leq 9$.
• Subtask 9 (8 pts): No special constraints.

Translated by ChatGPT 5