题目描述

小 C 正在赌博，初始时他有 $x$ 块钱，他的目标是赢到 $1$ 块钱。

每次他可以下注 $a$ 元，他有 $p$ 的概率获得返还的 $2a$ 元，同时有 $1-p$ 的概率啥也没有。

另外，由于小 C 上头了，他每次下注的钱不会少于上一次下注的钱。

你想知道小 C 在最优策略下有多少概率（或是收敛意义下概率）能赢到 $1$ 块钱。答案对 $10^9+7$ 取模，可以证明答案在模 $10^9+7$ 意义下一定收敛。

输入格式

第一行一个数字 $T$，表示数据组数。

接下来每组数据一行 $4$ 个整数 $a_1,b_1,a_2,b_2$，表示：

输出格式

对于每组数据，输出一行一个整数，表示答案对 $10^9+7$ 取模的结果。

样例 1 输入

5
1 4 1 4
3 4 1 4
1 3 1 3
53 128 123 456
114 514 191 9810

样例 1 输出

562500004
937500007
142857144
64906091
120102806

测试点约束

表格中的 $n,m$ 是 $[0,19]$ 中的一个整数。

对于 $100\%$ 的数据，保证：