The Stirling numbers of the second kind represent the number of ways to partition a set of $n$ elements into $m$ non-empty subsets. We denote this as $f(n, m)$.

The program uses a simple recurrence relation: $f(n, m) = f(n - 1, m - 1) + m f(n - 1, m)$, with initial values $f(0, 0) = 1$ and $f(0, m) = 0$ (for $m \neq 0$). The meaning of this recurrence is straightforward: either the $n$-th element forms a new subset by itself, or it is assigned to one of the existing $m$ subsets.

The program is as follows:

for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= min(i, m); ++j)
        f[i][j] = (f[i - 1][j - 1] +
        j * (long long)f[i - 1][j]) % 998244353;

(You may assume that out-of-bounds array accesses return 0, and the array is of size $(n + 1) \times (m + 1)$.)

Normally, the program should output $f(n, m) \pmod{998244353}$. However, a problem occurred: due to various reasons, after calculating $f(x, y)$, an unexpected memory write occurred, and $f(x, y)$ was assigned a value $z$. This event occurred a total of $k$ times for different $(x, y)$ pairs.

Given these $k$ unexpected events, output the actual value of $f(n, m) \pmod{998244353}$ produced by the program.

Input Format

The first line contains three integers $n, m, k$, as described above. The next $k$ lines each contain three integers $x_i, y_i, z_i$, representing that after $f(x_i, y_i)$ was calculated, its value was overwritten with $z_i$.

Output Format

Output a single integer representing the final value of $f(n, m) \pmod{998244353}$.

Examples

Input 1

5 3 1
1 0 1

Output 1

31

Input 2

1000 100 0

Output 2

958221900

Input 3

See broken/broken3.in and broken/broken3.ans in the contestant directory.

Subtasks

For 100% of the data, $1 \le x_i \le n \le 9 \times 10^8$, $0 \le y_i \le m \le \min(n, 10^5)$, $0 \le k \le 20$, $0 \le y_i \le x_i$, $0 \le z_i < 998244353$, and $(x_i < x_{i+1}) \lor (x_i = x_{i+1} \land y_i < y_{i+1})$.