분투

Nocriz는 여느 사람처럼 삶에 꿈을 품은 학생이다. 안타깝게도 삶은 늘 쉽지 않아서, 꿈이 멀게만 느껴지고 그것을 좇기 힘든 때가 있다.

현실은 종종 사람들을 꿈을 좇는 길에서 벗어나게 하고, 눈앞에 있는 것에 만족하게 만든다. 노력을 내려놓으라는 유혹을 받은 Nocriz가 Artemisia에게 말했다. "그래도 꿈을 포기하면 안 되겠지?" Artemisia가 대답했다. "당연히 꿈을 쉽게 포기하면 안 되지! 바위에 짓눌릴 때까지 버텨, 버티라고!"

그날 밤 Nocriz는 아주 나쁜 꿈을 꾸었다. 꿈속에는 타원 모양의 바위가 있었고, 그는 타원 안의 모든 정수 점 $(x, y)$에 대해 $(x \oplus y)^{33} x^{-2} y^{-1}$의 값을 모두 더한 합을 계산하라는 요청을 받았다. 계산은 $10^9 + 7$로 나눈 나머지에서 수행하며, $\oplus$는 비트 단위 XOR 연산이다.

타원은 여섯 정수 $a$, $b$, $c$, $d$, $e$, $f$로 정해진다. 타원을 $E = \{(x, y) \mid x, y \in \mathbb{Z}, \, a (x - b)^2 + c (y - d)^2 + e (x - b) (y - d) \le f\}$로 두자. 타원의 모든 점은 $0 < x, y < 4 \cdot 10^6$을 만족하고, 타원에는 정수 점이 적어도 하나 있다고 보장된다. 이제 좌표를 $10^9 + 7$로 나눈 나머지로 보고 다음 합을 구하라. $\sum_{(x, y) \in E} (x \oplus y)^{33} x^{-2} y^{-1}$ 여기서 수를 나머지로 본다는 것은 $z^{-1}$이 $z$의 모듈러 역원이며, 모든 덧셈과 곱셈의 결과를 $10^9 + 7$로 나눈 나머지로 취한다는 뜻이다.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10^4$)가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째이자 유일한 줄에 여섯 정수 $a$, $b$, $c$, $d$, $e$, $f$가 주어진다 ($1 \le a, c \le 100$, $-100 \le e \le 100$, $1 \le b, d \le 4 \cdot 10^6$, $0 \le f \le 10^{15}$). 타원의 모든 점 $(x, y)$는 $0 < x, y < 4 \cdot 10^6$을 만족하며, 타원에는 정수 점이 적어도 하나 있다고 보장된다.

모든 테스트 케이스에 걸쳐 $\max_{(x, y) \in E} \max(x, y)$의 합은 $4 \cdot 10^6$을 넘지 않는다고 보장된다.

각 테스트 케이스마다 답을 나타내는 정수를 한 줄에 출력한다. 계산에서 좌표는 $10^9 + 7$로 나눈 나머지로 취급해야 한다는 점을 잊지 마라.