Гонка роботів#8714

Гонка роботів

1 секунда

128 мегабайтів

Дуже складна

Сьогодні в Берляндії відбудеться щорічна гонка роботів, і Іван є одним із її учасників. Перед стартом він вирішив дізнатися, як виглядає поле, на якому змагатимуться роботи. Поле для гонки має форму прямокутника розміром $n \times m$ n \times m, розділеного на $nm$ одиничних клітинок. Рядки прямокутника пронумеровані від $1$ до $n$ , а стовпці - від $1$ до $m$ . Клітинка на перетині $i$ -го рядка і $j$ -го стовпця позначається як $(i, j)$ . Між кожною парою сусідніх клітинок на полі може бути бар'єр.

У гонці бере участь $n$ роботів. Спочатку вони розташовані в клітинках першого стовпця: $(1, 1)$ , $(2, 1)$ , ..., $(n, 1)$ . Фінішна клітинка знаходиться в позиції $(n, m)$ . Коли гонка починається, кожен робот починає рухатися в напрямку фінішу. З клітинки $(i, j)$ робот може переміститися або в клітинку $(i + 1, j)$ (i + 1, j), або в клітинку $(i, j + 1)$ (i, j + 1). Якщо між клітинкою, в якій знаходиться робот, і клітинкою, куди він переміщується, немає бар'єра, робот переміщується миттєво. Якщо ж між клітинками є бар'єр, робот витрачає одну секунду на переміщення.

Кожен робот заздалегідь знає, де на полі розташовані бар'єри, і вибирає шлях до фінішу, який займає мінімальний час. Роботи дуже малі, тому кілька роботів можуть одночасно перебувати в одній клітинці, не заважаючи один одному. Поле для змагань вважається справедливим, якщо мінімальний час, необхідний для досягнення фінішу з початкової позиції, однаковий для всіх роботів.

Іван встиг запам'ятати деяку інформацію про поле. Він знає, чи є бар'єр між деякими парами сусідніх клітинок. Також він упевнений, що поле є справедливим. Івану цікаво, скільки існує полів, що відповідають цим умовам. Оскільки відповідь може бути дуже великою, його цікавить лише залишок від ділення на $998244353$ .

Вхідні дані

Перша строка містить два цілих числа $n$ і $m$ - розміри поля для змагань ( $1 \leq n \leq 5$ 1 \le n \le 5, $1 \leq m \leq 15$ 1 \le m \le 15). Друга строка містить єдине число $k$ - кількість пар клітинок, про які Іван знає, чи є між ними бар'єр ( $0 \leq k \leq 2 nm - n - m$ 0 \le k \le 2nm - n - m).

Кожен з наступних $k$ рядків містить п'ять цілих чисел $r_{1}$ r_1, $c_{1}$ c_1, $r_{2}$ r_2, $c_{2}$ c_2 і $w$ ( $1 \leq r_{1} \leq r_{2} \leq n$ 1 \le r_1 \le r_2 \le n, $1 \leq c_{1} \leq c_{2} \leq m$ 1 \le c_1 \le c_2 \le m, $0 \leq w \leq 1$ 0 \le w \le 1). Якщо $w = 0$ w = 0, то між клітинками $(r_{1}, c_{1})$ (r_1, c_1) і $(r_{2}, c_{2})$ (r_2, c_2) немає бар'єра. Якщо $w = 1$ w = 1, то між клітинками є бар'єр. Гарантується, що клітинки $(r_{1}, c_{1})$ (r_1, c_1) і $(r_{2}, c_{2})$ (r_2, c_2) є сусідніми. Гарантується, що жодна пара сусідніх клітинок не буде згадана у вводі двічі.

Вихідні дані

Виведіть єдине число - залишок від ділення на $998244353$ кількості справедливих полів, які задовольняють усім умовам Івана.

Приклади

Приклад 1

Примітка

Тест з прикладу, суцільні лінії позначають бар'єр, а пунктирні - його відсутність.