Stirlingowe liczby drugiego rodzaju określają liczbę sposobów podziału $n$ elementów na $m$ niepustych zbiorów. Oznaczmy tę wartość jako $f(n, m)$.

Program, z którego korzysta Yi'ai, wykorzystuje prostą zależność rekurencyjną: $f(n, m) = f(n - 1, m - 1) + m \cdot f(n - 1, m)$, przy wartościach początkowych $f(0, 0) = 1$ oraz $f(0, m) = 0$ dla $m \neq 0$. Sens tej rekurencji jest łatwy do wyjaśnienia: albo $n$-ty element tworzy osobny zbiór, albo zostaje przydzielony do jednego z istniejących $m$ zbiorów.

Program Yi'ai wygląda następująco:

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;

(Można przyjąć, że wartości poza zakresem tablicy wynoszą 0, a w pamięci zaalokowano tablicę o rozmiarze $(n + 1) \times (m + 1)$).

Docelowo program Yi'ai powinien wypisać $f(n, m) \pmod{998244353}$, jednak wystąpił problem: z różnych przyczyn, po obliczeniu $f(x, y)$, zapis w pamięci uległ awarii i wartość $f(x, y)$ została nadpisana liczbą $z$. Takie zdarzenie wystąpiło łącznie $k$ razy dla różnych par $(x, y)$.

Oblicz, jaka będzie faktyczna wartość $f(n, m) \pmod{998244353}$ wypisana przez program po wystąpieniu tych $k$ awarii.

Wejście

W pierwszej linii wejścia znajdują się trzy liczby całkowite $n, m, k$, których znaczenie opisano powyżej.

W kolejnych $k$ liniach znajdują się po trzy liczby $x_i, y_i, z_i$, oznaczające, że po zakończeniu obliczeń $f(x_i, y_i)$ w pamięci zapisana została wartość $z_i$.

Wyjście

Wypisz jedną liczbę całkowią, oznaczającą faktyczny wynik $f(n, m) \pmod{998244353}$ uzyskany przez program.

Przykład 1

Wejście 1

5 3 1
1 0 1

Wyjście 1

31

Przykład 2

Wejście 2

1000 100 0

Wyjście 2

958221900

Przykład 3

Wejście 3

broken/broken3.in

Wyjście 3

broken/broken3.ans

Ograniczenia

Dla 100% danych wejściowych zachodzą warunki: $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$ oraz $(x_i < x_{i+1}) \lor (x_i = x_{i+1} \land y_i < y_{i+1})$.