滑冰

冬天到了，佳佳想去河上滑冰，但是渔民打鱼的时候在河面上开了好多冰洞。假设佳佳开始的位置为(0,0),想要滑行到(N,M)的位置。冰洞的位置已经勘察好了，在(X1,Y1),(X2,Y2),...,(XK,YK)的位置，佳佳技术不好只能绕过冰洞，并且佳佳每次只能沿着x轴或y轴的正方向移动距离1，统计一下佳佳可以有多少条路线。

输入的第一行为一个整数T (1<=T<=50)，表示测试用例的个数。
接下来输入T组数据，每组数据为：
第一行，两个整数N和M( N,M<=100,00 )。
第二行，一个整数K(K<=1000)表示有K个障碍。
第3到K+3行，2个整数Xi和Yi。

输出T行数据，每行一个整数，表示不同移动方式的数量除以124567的余数。

1
1 3
1
1 2

1

中科院计算所第二届“斯伦贝谢”杯Debug大赛