Гонка роботов
Сегодня в Берляндии состоится ежегодная гонка роботов. Иван - один из ее участников. Перед стартом он решил узнать, как выглядит поле, на котором будут соревноваться роботы. Поле для гонки представляет собой прямоугольник n * 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, j + 1). Если между клеткой, в которой находится робот, и клеткой, куда он перемещается, нет барьера, робот перемещается в соседнюю клетку мгновенно. Если же между клетками есть барьер, робот тратит одну секунду на перемещение между ними.
Каждый робот заранее знает, где на поле расположены барьеры, и двигается к финишной клетке по пути, время прохождения которого минимально. Роботы очень малы в размерах, поэтому несколько роботов могут находиться в одной клетке одновременно, не мешая друг другу. Назовем поле для соревнований справедливым, если минимальное время, необходимое для того, чтобы добраться до финиша из стартовой позиции, для всех роботов одинаково.
Иван успел окинуть взглядом поле для соревнований и запомнил некоторую информацию про него. А именно, про некоторые пары соседних клеток он точно знает, есть ли между ними барьер. Также он уверен, что поле для соревнований является справедливым. Ивану стало интересно, сколько всего существует полей, удовлетворяющих этим условиям. Так как ответ может быть очень большим, Ивана интересует лишь его остаток от деления на 998244353.
Входные данные
Первая строка содержит два целых числа n и m - размеры поля для сорвеновний (1 ≤ n ≤ 5, 1 ≤ m ≤ 15). Вторая строка содержит единственное число k - количество пар клеток, про которые Иван знает, есть ли между ними барьер (0 ≤ k ≤ 2nm - n - m).
Каждая из следующих k строк содержит пять целых чисел r[1], c[1], r[2], c[2] и w (1 ≤ r[1] ≤ r[2] ≤ n, 1 ≤ c[1] ≤ c[2] ≤ m, 0 ≤ w ≤ 1). Если w = 0, то между клетками (r[1], c[1]) и (r[2], c[2]) нет барьера. Если w = 1, то между клетками есть барьер. Гарантируется, что клетки (r[1], c[1]) и (r[2], c[2]) являются соседними. Гарантируется, что никакая пара соседних клеток не будет упомянута во вводе дважды.
Выходные данные
Выведите единственное число - остаток от деления на 998244353 количества справедливых полей, которые удовлетворяют всем условиям Ивана.
Пример
Тест из примера, сплошные линии обозначают барьер, а пунктирные - его отсутствие.
