seuOJ501 - Nanami and Trip Schemes Count Problem

题目描述

Nanami 来到了2d王国，不过，幸好她有神奇的嘉然手办，所以她没有被压扁，她现在需要尽快离开这个地方。Nanami 现在在 (1,1)(1,1)，每次她只能向上或向右移动一个单位，2d 王国的出口位于 (n,m)(n,m)。不仅如此，在2d平面的每个格点 (x,y)(x,y) 上都写有一个数字 00 或 11，共有 kk 个不同的格点 (xi,yi)(x_i,y_i) 上写着数字 11。在从起点到终点的过程中，Nanami 可以经过写着 00 的格点无数次，但最多只能经过写着 11 的格点 jj 次，（不然嘉然手办就会失效，她就会被压扁）。她想问你从起点到终点的方案数是多少。由于这个数可能非常大，因此只需求出方案数对于 998244353998244353 取模后的结果即可。

请注意，起点和终点的坐标可能相同。

在不走出2d平面边界的情况下，假如你当前位于坐标 (x,y)(x,y) 的点，那么你向上移动后的坐标会变为 (x,y+1)(x,y+1)，而假如你向右移动，那么你的坐标会变为 (x+1,y)(x+1,y)。

输入格式

第一行，一个整数 t(1≤t≤916)t(1\le t \le 916)，代表数据组数。

对于每组数据：

第一行，三个整数 n,m,k,j(1≤n,m≤106;0≤k≤min⁡(10,n×m);0≤j≤k)n,m,k,j(1\le n,m\le 10^6;0\le k \le \min(10,n\times m);0\le j \le k)，分别代表终点坐标 (n,m)(n,m) 、写着数字 11 的格点数量和 Nanami 最多可以经过写着 11 的格点数量。
接下来的 kk 行，每行两个整数 x,y(1≤x≤n;1≤y≤m)x,y(1\le x\le n;1\le y \le m)，代表一个写着 11 的格点坐标 (x,y)(x,y)，保证每一对坐标互不相同。

输出格式

对于每组数据，打印一行整数代表从起点到终点的方案数对于 998244353998244353 取模后的结果。

样例

输入样例

2
2 2 1 1
1 1
3 4 3 2
1 2
2 3
3 1

输出样例

2
10