G. T步

在 坐标平面上，横坐标与纵坐标都是整数的点叫做整点，由任一个整点(x,y)到整点(x+1,y+1)或(x+1,y-1)的有向线段叫做一个T步。

由整点 到整点 的一条T路是指由若干个T步组成的起点为 、终点为 的有向折线。

给定两个整点 和 ，求 到 的不经过x轴的T路的数量。答案对 取模。

注意:这道题目可能包含较大的输入数据量。在 Python 中，标准的 input() 函数速度较慢，可能导致超时。

解决方案： 请在代码开头添加以下两行来加速输入读取：

import sys
input = sys.stdin.readline

有多组测试数据。第一行输入一个整数 表示测试数据组数（）。对于每组测试数据：

第一行输入四个整数 ，，， （ ，），表示整点 和整点 。

输出 到 的不经过x轴的T路的数量。

Input：

6
0 1 2 1
0 2 4 2
0 1 2 -1
0 1 3 1
0 0 2 2
0 1 6 3

Output：

1
5
0
0
0
9