돌 게임

Chiaki는 다음과 같은 흥미로운 돌 게임을 생각해 냈다. 두 플레이어가 비어 있지 않은 두 개의 돌 더미에서 시작한다. 각 턴에서 플레이어는 돌이 짝수 개인 더미 하나를 골라 그 더미의 절반에 해당하는 돌을 다른 더미로 옮긴다. 더 이상 움직일 수 없거나 이미 나왔던 상태에 도달하면 게임이 끝난다. 전자의 경우 움직일 수 없는 플레이어가 진다. 후자의 경우 게임은 무승부로 선언된다.

두 양의 정수 $n$과 $m$이 주어질 때, Chiaki는 다음을 만족하는 쌍 $(a, b)$ ($1 \le a \le n, 1 \le b \le m$)의 개수를 알고 싶어 한다. 처음에 두 더미에 각각 $a$개와 $b$개의 돌이 있을 때 선공 플레이어가 이기는 전략을 가지거나, 게임이 무승부로 끝나거나, 후공 플레이어가 이기는 전략을 가지는 경우이다. 이 수는 매우 클 수 있으므로 $10^9+7$로 나눈 나머지만 계산하면 된다.

여러 개의 테스트 케이스가 주어진다. 입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$가 주어진다. 각 테스트 케이스에 대해:

첫 번째 줄에는 이진 문자열 $s$ ($1 \le |s| \le 10^6$)가 주어진다. 이는 앞에 불필요한 0이 없는 $n$의 이진 표현이다.

두 번째 줄에는 이진 문자열 $t$ ($1 \le |t| \le 10^6$)가 주어진다. 이는 앞에 불필요한 0이 없는 $m$의 이진 표현이다.

모든 테스트 케이스에서 이진 문자열 길이의 합은 $2 \times 10^6$을 넘지 않는다.

각 테스트 케이스에 대해 세 개의 정수를 출력한다. 이는 각각 선공 플레이어가 이기는 쌍 $(a, b)$의 개수, 게임이 무승부로 끝나는 쌍의 개수, 후공 플레이어가 이기는 쌍의 개수이다.

첫 번째 예제에 대해:

• 선공 플레이어가 이기는 쌍: $(2, 2)$, $(2, 4)$, $(2, 6)$, $(4, 2)$, $(4, 6)$, $(6, 2)$, $(6, 4)$, $(6, 6)$.
• 게임이 무승부로 끝나는 쌍: $(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)$.
• 후공 플레이어가 이기는 쌍: $(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)$.