23494번 - Stone Game 다국어

문제

Chiaki finds the following interesting stone game: two players start with two non-empty piles of stones. In each turn, the player can choose a pile with an even number of stones and move half of the stones of this pile to the other pile. The game ends if a player cannot move, or if we reach a previously reached position. In the first case, the player who cannot move loses. In the second case, the game is declared a draw.

Given two positive integers $n$ and $m,ドル Chiaki would like to know the number of pairs $(a, b)$ (1ドル \le a \le n, 1 \le b \le m)$ such that if initially the two piles have $a$ and $b$ stones respectively, then the first player has a winning strategy, or the game ends with a draw, or the second player has a winning strategy. Since this number may be very large, you are only asked to calculate it modulo 10ドル^9+7$.

입력

There are multiple test cases. The first line of the input contains an integer $T,ドル indicating the number of test cases. For each test case:

The first line contains a binary string $s$ (1ドル \le |s| \le 10^6$) -- the binary representation of $n$ without leading zeros.

The second line contains a binary string $t$ (1ドル \le |t| \le 10^6$) -- the binary representation of $m$ without leading zeros.

It is guaranteed that the sum of the length of binary strings in all test cases will not exceed 2ドル \times 10^6$.

출력

For each test case, output three integers: the number of pairs $(a, b)$ such that first player wins, the game ends with a draw or the second player wins, correspondingly.

제한

힌트

For the first sample:

• The pairs when first player wins: $(2, 2),ドル $(2, 4),ドル $(2, 6),ドル $(4, 2),ドル $(4, 6),ドル $(6, 2),ドル $(6, 4),ドル $(6, 6)$.
• The pairs when the game ends with draw: $(1, 2),ドル $(1, 4),ドル $(1, 6),ドル $(2, 1),ドル $(2, 3),ドル $(2, 5),ドル $(2, 7),ドル $(3, 2),ドル $(3, 4),ドル $(3, 6),ドル $(4, 1),ドル $(4, 3),ドル $(4, 5),ドル $(4, 7),ドル $(5, 2),ドル $(5, 4),ドル $(5, 6),ドル $(6, 1),ドル $(6, 3),ドル $(6, 5),ドル $(6, 7),ドル $(7, 2),ドル $(7, 4),ドル $(7, 6)$.
• The pairs when the second player wins: $(1, 1),ドル $(1, 3),ドル $(1, 5),ドル $(1, 7),ドル $(3, 1),ドル $(3, 3),ドル $(3, 5),ドル $(3, 7),ドル $(4, 4),ドル $(5, 1),ドル $(5, 3),ドル $(5, 5),ドル $(5, 7),ドル $(7, 1),ドル $(7, 3),ドル $(7, 5),ドル $(7, 7)$.