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$ 가 주어진다.

각 테스트 케이스의 첫째 줄에 양의 정수 $p$, $q$, $r$ 이 공백을 두고 주어진다.

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

• $1\le T\le 1\ 000$.
• $1\le p,\ q,\ r\le 10^7$.
• 모든 테스트 케이스에서 $p$의 합, $q$의 합, $r$의 합은 각각 $10^7$을 넘지 않는다.