20653번 - 롯데 자이언츠와 가희

문제

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

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

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

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

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

입력

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

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

출력

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

제한

• 1 ≤ T ≤ 100
• 2 ≤ n ≤ 10⁶
• 1 ≤ G, L ≤ 10⁹

힌트