P9387 [THUPC 2023 Finals] Chocolate

After you helped Little I completely beat Little J in the “Train Firing” game last time, Little J was very upset and decided to pull Little I into playing another game. This time, Little J found some chocolates he had收藏 (cáng). Little J prepared $(N + 1)$ chocolate bars. Except that the $(N + 1)$-th bar has $M$ pieces, each of the other $i$-th bars has exactly $i$ pieces. Little I moves first. The two players take turns. On each turn, the current player may do the following operation: - Choose one chocolate bar and split it into three ordered segments: left, middle, and right, where **each segment must contain an integer number of pieces, the middle segment must be non-empty, and the left and right segments may be empty**; - Eat the middle segment, and put the left and right segments back into the game. If, when it is a player’s turn, there are no chocolate bars left, then that player loses. At the start of the game, before Little I has time to work out the optimal strategy, Little J urges him to move quickly. So Little I has to **choose one operation uniformly at random among all legal operations**. Little J is well-prepared and always plays optimally. After this random move, Little I finally figures out the strategy, and from then on he also plays optimally on every turn. Little I wants to know: in the first random move, how many operations would allow him to win the game. The answer may be very large; you only need to output it modulo $(10^9+7)$. Two operations are considered different if and only if the chosen chocolate bar is different, or the numbers of pieces in any of the three ordered segments are different.

**This problem has multiple test cases.** The first line contains an integer $T$ denoting the number of test cases. Then the test cases follow. Each test case consists of one line with two integers $N, M$, with meanings as described above.

For each test case, output one line with an integer, representing the number of first moves that allow Little I to win, modulo $(10^9+7)$.

#### Sample Explanation - For the first test case, it is easy to prove that the first player is guaranteed to lose, so Little I will lose no matter what he does. - For the second test case, there are four operations: - Split the first chocolate bar into $(0,1,0)$, and eat the middle segment; - Split the fourth chocolate bar into $(0,1,0)$, and eat the middle segment; - Split the third chocolate bar into $(0,1,2)$, and eat the middle segment; - Split the third chocolate bar into $(2,1,0)$, and eat the middle segment. - For the third test case, all legal operations are to split the fourth chocolate bar into three segments where the left and right segments have the same length. - For the fourth test case, the game is just a cover; Little J only wants Little I to lose. #### Constraints This problem has only one test point with $T = 5 \times 10^4$. For each test case, $0 \le N,M \le 10^{18}$. #### Afterword “Can I continue playing games with you next time……” #### Source From the 2023 Tsinghua University Student Algorithmic Contest and Intercollegiate Invitational (THUPC2023) Finals. Solutions and other resources can be found at . Translated by ChatGPT 5