: ^은 무엇인가요?
- 피돌이 : 이요!
- 수돌이 : 이요!
퀴즈 대회에서 이 질문에 대해 피돌이는 ^를 XOR()로 보아서 을 답했고 수돌이는 ^를 지수를 나타내는 로 보아서 이라고 답했다. 이런 혼선을 막기 위해, 퀴즈 대회의 출제자는 ^를 XOR로 볼 때와 지수로 볼 때의 답이 같도록 문제를 만들기로 했다. 하지만 두 개의 수에 대해서 문제를 만드는 것은 너무 쉽다고 생각한 퀴즈 출제자는, 다음과 같이 만들 문제를 바꿨다.
첫째 줄에 테스트 케이스의 개수 가 주어진다.
각 테스트 케이스의 첫째 줄에 양의 정수 , , 이 공백을 두고 주어진다.
각 테스트 케이스의 첫째 줄에 세 값 로 가능한 경우의 수를 로 나눈 나머지를 출력한다.
첫 번째 테스트케이스에서, 로는 이 가능하다.
, , 는 각각 을 만족하는 양의 정수일 때, 위 조건을 만족하는 세 값 로 가능한 경우의 수를 구해보자. 단, 답이 너무 커질 수 있으므로 답을 로 나눈 나머지를 구해보자.
두 번째 테스트케이스에서, 로는 이 가능하다.
