| 问题描述 |
|---|
国王为了奖励两个有功劳的将军，拿出了两个国际象棋棋盘，在每个棋盘都分别做了如下操作： 在第一格放了$$1$$粒米，然后第二格放了$$2$$粒米，第三格放了$$4$$粒米，第四格放了$$8$$粒米，...，第$$63$$格放了$$2^{62}$$粒米，第$$64$$格放了$$2^{63}$$粒米。 然后让两位将军各自针对属于自己的那一个棋盘，取走其中若干格里放置的所有米。 两位将军有各自喜欢的数字和不喜欢的数字，所以取走米的格子可能不尽相同，有时也会出现某一位将军特别谦虚以至于不取走任何格子上的米的情况。 已知两位将军取走的米粒总和，以及他们共同选择的格子数量，求两位将军有多少种不同的取走米的方案？ 注意，第一个将军选择第$$x$$格而第二个将军不选择第$$x$$格，与第一个将军不选第$$x$$格而第二个将军选择第$$x$$格，是不同的方案。 |
| 输入描述 |
一个正整数$$n$$，表示案例的数量。（$$1 \le n \le 15$$） 每组案例由一个整数$$a$$和$$b$$组成含义见描述。（$$1 \le a \le 2^{64}-1，0 \le b \le 64$$） |
| 输出描述 |
针对每组案例，输出一个整数，表示不同的取米方案数量除以$$10^8+7$$的余数。 如果没有可行方案，那么输出$$0$$。 |
| 样例输入复制样例 |
3 8 1 8 2 1234567890 12 |
| 样例输出 |
7 0 16530885 |
| 提示说明 |
在第一组案例中，两位将军共选了$$8$$粒米，且共同选择的格子数量是$$1$$，所有可能的解是： 1、$$A$$将军选择$$1+2$$，$$B$$将军选择$$1+4$$； 2、$$A$$将军选择$$1+4$$，$$B$$将军选择$$1+2$$； 3、$$A$$将军选择$$1$$，$$B$$将军选择$$1+2+4$$； 4、$$A$$将军选择$$1+2+4$$，$$B$$将军选择$$1$$； 5、$$A$$将军选择$$2$$，$$B$$将军选择$$2+4$$； 6、$$A$$将军选择$$2+4$$，$$B$$将军选择$$2$$； 7、$$A$$将军选择$$4$$，$$B$$将军选择$$4$$。 共有$$7$$种不同的选择方案。 在第二组案例中，两位将军共选了$$8$$粒米，且共同选择的格子数量是$$2$$，无解。 |
| 相关 |