Предыстория

«Из моей маленькой и тесной комнаты» «От моей кровати, полной жадности» «В мир, где всегда есть место» «Но всё разбилось, разбилось» — «Разбитая мечта» (Broken Dream), COP, Ло Тяньи

Спустя много лет, чем стали олимпиадные задачи для Иай? Лишь ярким, но незаконченным сном. Вечным сном, потерянным сном, безнадежным сном, разбитым сном. Словно что-то вспомнив, она достала из коробки покрытый пылью блокнот и с трудом нашла зарядное устройство от старой эпохи. Под гул вентилятора перед ней вновь предстал забытый мир. Ей казалось, что стоит лишь взглянуть на задачу, и она сможет распутать её нити, но это было лишь самообманом. «Как там вычисляются числа Стирлинга второго рода?» — внезапно всплыло у неё в голове. Да, когда-то она была глубоко погружена в комбинаторные вычисления, но теперь она забыла даже основы.

Описание задачи

Числа Стирлинга второго рода — это количество способов разбить $n$ элементов на $m$ непустых подмножеств. Далее мы будем обозначать это число как $f(n, m)$.

Программа Иай использует простую рекуррентную формулу: $f(n, m) = f(n - 1, m - 1) + m f(n - 1, m)$, с начальными значениями $f(0, 0) = 1, f(0, m) = 0$ при $m \neq 0$. Смысл этой формулы несложен: либо $n$-й элемент образует отдельное подмножество, либо он распределяется в одно из уже существующих $m$ подмножеств.

Программа Иай выглядит так:

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;

(Можно считать, что значения вне границ массива равны 0, а размер массива составляет $(n + 1) \times (m + 1)$).

В конечном итоге программа Иай должна была вывести $f(n, m) \pmod{998244353}$, но возникла проблема: по разным причинам после вычисления $f(x, y)$ произошла ошибка записи в память, и значение $f(x, y)$ было заменено на число $z$. Такие события произошли в общей сложности $k$ раз для различных пар $(x, y)$.

Определите, какое значение $f(n, m) \pmod{998244353}$ фактически выдаст программа Иай после этих $k$ ошибок.

Входные данные

В первой строке содержатся три целых числа $n, m, k$, смысл которых описан выше.

Далее следуют $k$ строк, каждая из которых содержит три числа $x_i, y_i, z_i$, означающих, что после завершения вычисления $f(x_i, y_i)$ в памяти было записано значение $z_i$.

Выходные данные

Выведите одно целое число — итоговый результат $f(n, m) \pmod{998244353}$, полученный программой.

Примеры

Входные данные 1

5 3 1
1 0 1

Выходные данные 1

31

Входные данные 2

1000 100 0

Выходные данные 2

958221900

Входные данные 3

broken/broken3.in

Выходные данные 3

broken/broken3.ans

Ограничения

Для всех тестов гарантируется: $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$, $(x_i < x_{i+1}) \lor (x_i = x_{i+1} \land y_i < y_{i+1})$.

Подзадачи