셜록과 왓슨의 헬스장 비밀 (Large)

왓슨과 셜록은 같이 운동하는 헬스장 친구다.

헬스 트레이너는 두 사람에게 세 정수 $A$, $B$, $N$을 주고, $N$ 이하의 서로 다른 양의 정수 $i$와 $j$를 고르라고 했다. 왓슨은 매일 새싹을 정확히 $i^A$개 먹어야 하고, 셜록은 매일 정확히 $j^B$개 먹어야 한다.

왓슨과 셜록은 어느 날 두 사람이 먹은 새싹 개수의 합이 어떤 정수 $K$로 나누어떨어지면 그날은 사이좋게 지낸다는 사실을 알아냈다.

$i \ne j$이면서 $i^A + j^B$가 $K$로 나누어떨어지는 쌍 $(i, j)$가 몇 개인지 구하라. 쌍은 순서를 구분하므로 $(1, 2)$와 $(2, 1)$은 서로 다른 쌍이다. 쌍의 개수가 매우 클 수 있으므로 $10^9+7$ ($1000000007$)로 나눈 나머지를 출력한다.

$i$와 $j$는 양의 정수이므로 $A = 0$이면 $i^A = 1$이고, $B = 0$이면 $j^B = 1$이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 이루어지며, 앞에서 설명한 네 정수 $A$, $B$, $N$, $K$가 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 구하는 답이다.

• $1 \le T \le 100$
• $0 \le A \le 10^6$
• $0 \le B \le 10^6$
• $1 \le K \le 100000$
• $1 \le N \le 10^{18}$

예제의 첫 번째 테스트 케이스에서 가능한 쌍은 $(1, 2)$, $(1, 5)$, $(2, 1)$, $(2, 4)$, $(4, 2)$, $(4, 5)$, $(5, 1)$, $(5, 4)$이다.

두 번째 테스트 케이스에서 가능한 쌍은 $(1, 2)$, $(1, 3)$, $(4, 1)$이다.

세 번째 테스트 케이스에서는 $i \ne j$ 조건 때문에 가능한 쌍이 없다.