Xiaowang 身处一张 大小的地图中。地图最左上角的坐标为 (1, 1)，最右下角的坐标为 (n, m)。地图中有 k 个障碍物，每个障碍物放的位置由坐标表示，障碍物占用坐标所在的一格。除了障碍物，地图中都是空地。
Xiaowang 可以在相邻的空地间自由穿梭，但不可以走出地图，也不可以走到障碍物上。我们称坐标 和坐标 是相邻的，当且仅当 。
Xiaowang 想知道有多少无序对 满足：他可以从其中一个点出发并且能够到达另一个点。
由于答案可能很大，因此你只需要求出它答案对 取模后的结果。

输入描述:

第一行包含一个整数 T () 表示测试数据的组数。 对于每组测试数据：
第一行包含两个整数 n, m ()，中间以空格分隔，分别表示地图行数和列数。
第二行包含一个整数 k ()，表示障碍物的数量。
接下来 k 行，每行包含两个整数 ,  ( , ,)，中间以空格分隔，表示第 i 个障碍物的坐标。
输入保证 。

输出描述:

对于每组测试数据，在一行输出一个整数，表示点对的数量对  取模后的结果。

2
2 2
1
1 2
200000 200000
0

6
39060

备注:

对于第一个样例：
如果用 0 表示空地，用 1 表示障碍物，则地图可以表示为:

符合题目要求的点对有 6 个： 
{(1, 1), (1, 1)} , {(2, 1), (2, 1)} , {(2, 2), (2, 2)} , {(1, 1), (2, 1)} , {(1, 1), (2, 2)} , {(2, 1), (2, 2)}。 
对于第二个样例：
符合题目要求的点对有  个。
对  取模后结果为 。

注意起点和终点同样应该是空地，否则 Xiaowang 就会被困在障碍物中。