卒过河过不了一点。
有一个二维平面,你从原点 (0,0) 出发,每次只能向上或向右移动一个单位,目的地的坐标为 (n,m),你在移动过程中不能走出平面边界。但在点 (x,y) 上有一障碍物,你不能进入或者经过 (x,y) 这个点。求到达目的地的方案数。
假如你当前位于坐标 (x,y) 的点,那么你向上移动后的坐标会变为 (x,y+1),而假如你向右移动,那么你的坐标会变为 (x+1,y)。
第一行输入一个整数 t(1≤t≤103) ,代表数据组数。
接下来的 t 行,每行输入四个整数 x,y,n,m(1≤x≤n≤1000;1≤y≤m≤1000),分别代表障碍物的坐标和目的地的坐标。
对于每组数据,输出从起点到终点的方案数,因为方案数可能很多,你只需要输出答案对于 998244353 取模后的结果即可。
输入样例
6
1 1 2 2
2 2 3 3
1 2 3 4
2 1 3 4
114 514 233 666
1000 1000 1000 1000
输出样例
2
8
17
23
871640904
0
提示
在样例的第 1 组数据中,有 2 条路线,分别是 (0,0)−>(0,1)−>(0,2)−>(1,2)−>(2,2) 和 (0,0)−>(1,0)−>(2,0)−>(2,1)−>(2,2)。