로봇 경주

매년 열리는 로봇 경주가 오늘 베를란드에서 열린다. 이반도 참가자 중 한 명이다. 경주가 시작되기 전에 그는 경기장이 어떻게 생겼는지 알아보려 한다.

경기장은 $n \times m$ 크기의 직사각형이며, 단위 칸 $nm$개로 나뉘어 있다. 행은 1부터 $n$까지, 열은 1부터 $m$까지 번호가 매겨진다. $(i, j)$는 $i$행 $j$열의 칸을 뜻한다. 인접한 두 칸 사이에는 장애물이 있을 수도 있고 없을 수도 있다.

로봇은 $n$대이며, 경주 전에는 첫 번째 열의 칸 $(1, 1), (2, 1), \ldots, (n, 1)$에 놓여 있다. 결승점은 $(n, m)$ 칸이다. 경주가 시작되면 각 로봇은 결승점을 향해 움직인다. 칸 $(i, j)$에서 로봇은 $(i + 1, j)$ 또는 $(i, j + 1)$로 이동할 수 있다. 두 칸 사이에 장애물이 없으면 로봇은 즉시 이동한다. 장애물이 있으면 이동에 1초가 걸린다.

각 로봇은 장애물의 위치를 미리 모두 알고 있으며, 결승점에 가장 적은 시간이 걸리는 경로를 택한다. 로봇은 매우 작아서 여러 대가 같은 칸에 있을 수 있다. 모든 로봇이 결승점에 도달하는 데 걸리는 시간이 같으면 그 경기장을 공정하다고 한다.

이반은 경기장을 한 번 보았고 몇 가지 정보를 기억하고 있다. 일부 인접한 칸 쌍에 대해서는 그 사이에 장애물이 있는지 없는지 확실히 알고 있다. 또한 경기장이 공정하다는 것도 확실하다. 이반은 이 조건을 모두 만족하는 경기장이 몇 개인지 알고 싶어 한다. 답이 매우 클 수 있으므로 998244353으로 나눈 나머지를 구한다.

첫 줄에 경기장의 크기 $n$과 $m$이 주어진다 ($1 \le n \le 5$, $1 \le m \le 15$).

둘째 줄에는 이반이 장애물 여부를 알고 있는 칸 쌍의 개수 $k$가 주어진다 ($0 \le k \le 2nm - n - m$).

다음 $k$개의 줄에는 다섯 정수 $r_1$, $c_1$, $r_2$, $c_2$, $w$가 주어진다 ($1 \le r_1 \le r_2 \le n$, $1 \le c_1 \le c_2 \le m$, $0 \le w \le 1$). $w = 0$이면 칸 $(r_1, c_1)$과 $(r_2, c_2)$ 사이에 장애물이 없고, $w = 1$이면 장애물이 있다. 주어지는 두 칸은 항상 인접하며, 같은 칸 쌍이 두 번 이상 주어지지 않는다.

이반의 조건을 모두 만족하는 공정한 경기장의 개수를 998244353으로 나눈 나머지를 한 줄에 출력한다.

그림은 예제에 대한 설명이다. 실선은 장애물을, 점선은 장애물이 없음을 나타낸다.