셜록과 왓슨의 체육관 비밀

왓슨과 셜록은 함께 체육관에 다니는 친구다.

체육관 트레이너는 이들에게 세 수 A, B, N을 주고, 왓슨과 셜록에게 서로 다른 두 양의 정수 i와 j를 고르라고 했다. 이때 i와 j는 모두 N 이하이다. 왓슨은 매일 정확히 $i^{A}$개의 방울양배추를 먹어야 하고, 셜록은 매일 정확히 $j^{B}$개의 방울양배추를 먹어야 한다.

왓슨과 셜록은 어떤 날 둘이 먹은 방울양배추의 총개수가 특정 정수 K로 나누어떨어지면 그날 서로 사이좋게 지낸다는 사실을 알아냈다.

따라서 왓슨과 셜록은 i != j인 이러한 순서쌍 (i, j)가 몇 개 존재하는지 알아내기 위해 여러분의 도움이 필요하다. 순서쌍의 수가 매우 클 수 있으므로, 이를 $10^{9}$+7 (1000000007)로 나눈 나머지를 출력한다.

제한

1 ≤ T ≤ 100. 테스트 세트당 시간 제한: 60초. 메모리 제한: 1GB. 0 ≤ A ≤ $10^{6}$. 0 ≤ B ≤ $10^{6}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ K ≤ 10000. 1 ≤ N ≤ 1000.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ K ≤ 100000. 1 ≤ N ≤ $10^{18}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 정수 A, B, N, K 4개가 있는 한 줄로 이루어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 요구되는 답이다.

케이스 1에서 가능한 순서쌍은 (1, 2), (1, 5), (2, 1), (2, 4), (4, 2), (4, 5), (5, 1), 그리고 (5, 4)이다. 케이스 2에서 가능한 순서쌍은 (1, 2), (1, 3), 그리고 (4, 1)이다. 케이스 3에서는 i != j이므로 가능한 순서쌍이 없다.