Placing Stones
题目描述
现有A,B两堆石子，初始时分别有\(s_A, s_B\)粒。每次可以执行如下两种操作之一：
（1）将A堆中一半（向下取整，下同）的石子加到B堆中，然后在A堆上补加一粒石子；
（2）将B堆中一半的石子加到A堆中，然后在B堆上补加一粒石子。
要求若干次操作之后，两堆的石子数分别变为\(t_A, t_B\)，求共有多少种操作方案。
I/O格式
输入
第一行是一个正整数\(T\)，表示数据的组数；
之后\(T\)行，每行一组测试数据，包含4个正整数\(s_A, s_B, t_A, t_B\)，保证\(s_A, s_B, t_A, t_B \ge 2\)。
输出
每组数据输出一行，方案数对\(10^5 + 3\)取模后的结果。
样例
输入
3
3 6 9 6
4 15 9 16
2 100 50 58
输出
8
4
1
数据规模及约定
50%的数据：\(2 \le s_A, s_B, t_A, t_B \le 10\)
100%的数据：\(T \le 10, \quad 2 \le s_A, s_B, t_A, t_B \le 1000\)
时间限制1s，空间限制256MB。
