Placing Stones

Placing Stones

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

现有A,B两堆石子,初始时分别有sA,sBs_A, s_B粒。每次可以执行如下两种操作之一:
(1)将A堆中一半(向下取整,下同)的石子加到B堆中,然后在A堆上补加一粒石子;
(2)将B堆中一半的石子加到A堆中,然后在B堆上补加一粒石子。
要求若干次操作之后,两堆的石子数分别变为tA,tBt_A, t_B,求共有多少种操作方案。

I/O格式

输入

第一行是一个正整数TT,表示数据的组数;
之后TT行,每行一组测试数据,包含4个正整数sA,sB,tA,tBs_A, s_B, t_A, t_B,保证sA,sB,tA,tB2s_A, s_B, t_A, t_B \ge 2

输出

每组数据输出一行,方案数对105+310^5 + 3取模后的结果。

样例

输入

3
3 6 9 6
4 15 9 16
2 100 50 58

输出

8
4
1

数据规模及约定

50%的数据:2sA,sB,tA,tB102 \le s_A, s_B, t_A, t_B \le 10
100%的数据:T10,2sA,sB,tA,tB1000T \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