1375:阔绰的国王-2

国王为了奖励两个有功劳的将军，拿出了两个国际象棋棋盘，在每个棋盘都分别做了如下操作：在第一格放了1粒米，然后第二格放了2粒米，第三格放了4粒米，第四格放了8粒米，...，第63格放了2^62粒米，第64格放了2^63粒米。然后让两位将军各自针对属于自己的那一个棋盘，取走其中若干格里放置的所有米。两位将军有各自喜欢的数字和不喜欢的数字，所以取走米的格子可能不尽相同，有时也会出现某一位将军特别谦虚以至于不取走任何格子上的米的情况。已知两位将军取走的米粒总和，以及他们共同选择的格子数量，求两位将军有多少种不同的取走米的方案？

注意，第一个将军选择第x格而第二个将军不选择第x格，与第一个将军不选第x格而第二个将军选择第x格，是不同的方案。

方案的数量可能非常多，要求输出方案数量除以1e8+7的余数。

一个正整数n，表示案例的数量。（n<=15）

每组案例由一个整数a和b组成（1<=a<=2^64-1，0<=b<=64），a表示两位将军取走的米粒总和，b表示两位将军共同选择的格子数量。

针对每组案例，输出一个整数，表示不同的取米方案数量除以1e8+7的余数。如果没有可行方案，那么输出0。

每组案例输出完要换行。

3

8 1

8 2

1234567890 12

7

0

16530885

在第一组案例中，两位将军共选了8粒米，且共同选择的格子数量是1，所有可能的解是：A将军选择1+2，B将军选择1+4；A将军选择1+4，B将军选择1+2；A将军选择1，B将军选择1+2+4；A将军选择1+2+4，B将军选择1；A将军选择2，B将军选择2+4；A将军选择2+4，B将军选择2；A将军选择4，B将军选择4。共有7种不同的选择方案。

在第二组案例中，两位将军共选了8粒米，且共同选择的格子数量是2，无解。