시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 512 MB 55 24 17 50.000%

문제

작년 7월 28일, 야구 시즌에는 항상 그랬듯, 가희는 롯데 야구를 보고 있었습니다. 그런데 갑자기, TV 화면에 수학 문제 T 개가 나타났습니다.

9회 말이 막 시작해서 당황한 가희는 여러분들에게 TV 화면에 나타난 [문제] T 개를 빠르게 풀어 달라고 요청하였습니다.

[문제] 조건을 만족하는 수열의 개수를 구해주세요.

  • 수열의 길이는 n 입니다.
  • 수열에 있는 모든 수는 0보다 큰 자연수입니다.
  • 수열에 있는 수들의 최대공약수는 G 입니다.
  • 수열에 있는 수들의 최소공배수는 L 입니다.

[문제]는 TV 화면에서 n G L 1줄로 표시됩니다.

입력

첫째 줄에 TV 화면에 나타난 문제의 수 가 주어집니다.

둘째 줄부터 T+1 번째 줄까지, TV 화면에 나타난 문제에 대한 정보가 n G L의 형식으로 입력됩니다. 이 수들은 공백으로 구분됩니다.

출력

각 문제에 대한 답을 109+7 (1,000,000,007)로 나눈 나머지를 한 줄에 하나씩 출력하세요.

제한

  • 1 ≤ ≤ 100
  • 2 ≤ n ≤ 106
  • 1 ≤ G, L ≤ 109

예제 입력 1

2
2 6 12
3 12 10

예제 출력 1

2
0

첫 번째 테스트 케이스의 경우, 문제의 조건을 만족하는 수열은 [6, 12], [12, 6] 의 2가지입니다.

두 번째 테스트 케이스의 경우, 조건을 만족하는 수열은 존재하지 않습니다.

출처