33614번 - 2^3은?

문제

$Q$: 2ドル$^3ドル$은 무엇인가요?

피돌이: 1ドル$이요!

수돌이: 8ドル$이요!

퀴즈 대회에서 이 질문에 대해 피돌이는 ^를 XOR($\oplus$)로 보아서 2ドル\oplus 3=1$을 답했고 수돌이는 ^를 지수를 나타내는 2ドル^3$로 보아서 8ドル$이라고 답했다. 이런 혼선을 막기 위해, 퀴즈 대회의 출제자는 ^를 XOR로 볼 때와 지수로 볼 때의 답이 같도록 문제를 만들기로 했다. 하지만 두 개의 수에 대해서 문제를 만드는 것은 너무 쉽다고 생각한 퀴즈 출제자는, 다음과 같이 만들 문제를 바꿨다.

• 세 개의 수 $a,\ b,\ c$에 대해 피돌이와 수돌이가 계산하는 $a$ ^ $b$ ^ $c$ 값이 같아야 한다.
• 피돌이는 ^기호를 항상 XOR로 본다. 즉 $a$ ^ $b$ ^ $c$를 $a\oplus b\oplus c$로 계산한다.
• 수돌이는 ^기호를 항상 지수로 본다. 즉 $a$ ^ $b$ ^ $c$를 $a^{b^c}$로 계산한다. $a^{b^c}$를 계산할 때는 먼저 $b^c$를 계산한 후 이 값이 $a$의 지수에 있다고 생각하여 계산한다.

$a,ドル $b,ドル $c$는 각각 $a\le p,\ b\le q,\ c \le r$을 만족하는 양의 정수일 때, 위 조건을 만족하는 세 값 $(a,b,c)$로 가능한 경우의 수를 구해보자. 단, 답이 너무 커질 수 있으므로 답을 1ドル,000円,000円,007円$로 나눈 나머지를 구해보자.

입력

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

각 테스트 케이스의 첫째 줄에 양의 정수 $p,ドル $q,ドル $r$ 이 공백을 두고 주어진다. $(1\le p,\ q,\ r\le 10^7)$

모든 테스트 케이스에서 $p$의 합, $q$의 합, $r$의 합은 각각 10ドル^7$을 넘지 않는다.

출력

각 테스트 케이스의 첫째 줄에 세 값 $(a,\ b,\ c)$로 가능한 경우의 수를 1ドル,000円,000円,007円$로 나눈 나머지를 출력한다.

제한

힌트