Little D has $n$ buckets, each made of $m$ wooden planks of distinct types. For a bucket with plank lengths $a_1, a_2, \dots, a_m$, the volume of liquid it can hold is $\min_{i=1}^m a_i$.

Little D's $n$ buckets are magical; the total profit they generate is not simply the sum of the liquid volumes of each bucket, but the product of the liquid volumes of all buckets. That is, for these $n$ buckets, if the height of the $j$-th plank of the $i$-th bucket is $p_{j,i}$, the profit generated is $\prod_{i=1}^n (\min_{j=1}^m p_{j,i})$.

Little D has purchased some planks from a lumber yard, but the supply 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 already placed $q$ planks, but has not yet decided how to place the remaining ones. He wants you to calculate the sum of the profits over all valid ways to place the remaining planks. Since this number can be very large, output the result modulo $998244353$.

Formal Problem Statement

There are $m$ permutations of length $n$, where $q$ positions have fixed values, and the remaining positions are undetermined. Calculate the sum of $\prod_{i=1}^n (\min_{j=1}^m p_{j,i})$ over all distinct sets of permutations. Output the result modulo $998244353$. Two sets of permutations $P$ and $Q$ are distinct 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 configuration exists.

Input

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

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

Output

Output a single integer representing the sum of profits of all valid configurations modulo $998244353$.

Examples

Input 1

2 2 0

Output 1

6

Input 2

3 2 1
1 1 1

Output 2

38

Input 3

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

Output 3

830538815

Constraints

This problem uses bundled testing.

For all data, $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, q\leq 5$.
• Subtask 2 (8 pts): $n\leq 7, m\leq 3, q\leq 5$.
• 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.