题目描述

上回你帮小 I 在开火车上薄纱小 J 后，小 J 十分不服气，决定拉上小 I 再玩玩别的游戏。这次小 J 找到了他家珍藏的巧克力。

小 J 准备了 $(N + 1)$ 条巧克力，其中除了第 $(N + 1)$ 条巧克力有 $M$ 块外，其他第 $i$ 条巧克力恰好有 $i$ 块。

游戏由小 I 先手，双方轮流操作，每次操作方可以进行如下操作：

• 选择一条巧克力，将其分成左中右有序的三段，其中每段必须有整数块，中间一段不能为空，左右两段可以为空；
• 将中间一段吃掉，左右两段放回游戏。

当某个人操作时没有巧克力了，那个人就输了。

游戏开始，小 I 还没来得及算好最优策略小 J 就连忙催促，于是小 I 只好在所有的合法操作中等概率随机选择一个进行操作。小 J 自然是有备而来，每次操作都是最优的；而在这次随机操作之后，小 I 也终于是算清楚了游戏策略，之后的每次操作都是最优的。

小 I 想知道，第一次的随机操作中，有多少种操作能够让他取得游戏胜利。答案可能很大，你只需要输出其对 $(10^9+7)$ 取模的结果。

认为两个操作不同当且仅当选择的巧克力不同或巧克力分成的有序的三段的块数有一段不同。

输入格式

本题有多组测试数据。 第一行一个整数 $T$ 表示测试数据组数。接下来依次输入每组测试数据。

每组测试数据一行两个整数 $N,M$，意义如题目描述所述。

输出格式

对于每组测试数据输出一行一个整数，表示能使小 I 胜利的第一次操作数对 $(10^9+7)$ 取模。

4
3 0
3 1
3 12345678987654321
0 0

0
4
450617288
0

提示

样例解释

• 对于第一组测试数据，容易证明先手必败，所以无论怎么操作小 I 都会输。
• 对于第二组测试数据，有以下四种操作：
  • 将第一条巧克力分成 $(0,1,0)$ 三段，将中间一段吃掉；
  • 将第四条巧克力分成 $(0,1,0)$ 三段，将中间一段吃掉；
  • 将第三条巧克力分为 $(0,1,2)$ 三段，将中间一段吃掉；
  • 将第三条巧克力分为 $(2,1,0)$ 三段，将中间一段吃掉。
• 对于第三组测试数据，所有的合法操作都是将第四条巧克力分成三段，其中左右两段长度相同。
• 对于第四组测试数据，游戏只是个幌子罢了，小 J 只是想小 I 输。

数据范围

本题仅有一个 $T = 5 \times 10^4$ 的测试点，对于每组测试数据 $0 \le N,M \le 10^{18}$。

后记

“下次能继续和你玩游戏吗……”

题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2023 查看。