Placing Stones

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。

2019.1.31补题通道

未参加
状态
已结束
规则
ACM/ICPC
题目
3
开始于
2019-01-31 17:30
结束于
2019-02-10 00:00
持续时间
222.5 小时
主持人
参赛人数
27