题目描述

继《铺瓷砖》以后，Sam 就开始思考，为什么一定要把地面铺满才是好看的呢？

Sam 认为有时候有一些缺陷，才会更完美。

于是 Sam 决定敲掉一些瓷砖！

也就是说 Sam 有一个 $n * m$ 大小的地板，每个格子内都铺满了瓷砖，现在 Sam 有一个大小为 $1 * 2$ 的锤子，也就是一锤会同时敲掉两个相邻的瓷砖（可以是竖着也可以是横着）。

当然，Sam 希望地板是有一些缺陷使得更加完美，而不是让地板彻底被损坏。

所以他提出了一个要求，他希望在最后，地板的每一行和每一列都满足以下情况之一：

1. 这一行或者这一列是完整的，没有被敲掉瓷砖。
2. 这一行或者这一列只被敲掉了一块瓷砖。
3. 如果这一行或者这一列被敲掉了两块瓷砖，那么这两块瓷砖必须是同时被敲掉的（也就是出自同一次敲瓷砖的操作）。

现在 Sam 想知道，他一共会有多少种敲瓷砖的方案？

当然，由于这个问题过于简单，所以 Sam 会提前敲 $k$ 次瓷砖，并且他会告诉你每一次敲的是哪两块瓷砖。

输入格式

输入第一行包含三个整数 $n,m,k$ 表示地板大小以及 Sam 提前敲瓷砖的次数。

接下来 $k$ 行，每行四个整数 $x_1,y_1,x_2,y_2$ 分别表示 Sam 这一次敲的两块瓷砖分别为 $(x_1,y_1),(x_2,y_2)$。

输出格式

告诉 Sam 在他敲过 $k$ 次以后，还存在多少种不同的敲瓷砖方案，由于答案可能很大，请将答案对 $998244353$ 取模。

输入输出样例 #1

输入 #1

4 4 0

输出 #1

85

输入输出样例 #2

输入 #2

4 5 1
3 3 3 4

输出 #2

8

输入输出样例 #3

输入 #3

18 18 2
4 10 5 10
11 5 11 6

输出 #3

771975612

说明/提示

数据范围

对于所有数据满足 $1 \leq n,m \leq 4000, 0\leq k \leq 2500$。

保证给出的 $x_1,x_2,y_1,y_2$ 一定合法，且每次敲瓷砖给出的两个瓷砖必然相邻。

样例解释2

敲瓷砖的方案分别为：

1. 什么都不敲。
2. 敲一次：$(1,1),(1,2)$。
3. 敲一次：$(1,1),(2,1)$。
4. 敲一次：$(1,2),(2,2)$。
5. 敲一次：$(2,1),(2,2)$。
6. 敲一次：$(4,1),(4,2)$。
7. 敲一次：$(1,5),(2,5)$。
8. 敲两次：$(4,1),(4,2)$ 和 $(1,5),(2,5)$。