롯데 자이언츠와 가희
시간 제한0.5초메모리 제한512 MB
길이가 n인 양의 정수 수열 가운데 최대공약수가 G이고 최소공배수가 L인 것의 개수를 1e9+7로 나눈 나머지로 구한다.
문제
작년 7월 28일, 야구 시즌에는 늘 그렇듯 가희는 롯데 야구를 보고 있었습니다. 그런데 갑자기 TV 화면에 수학 문제 T개가 나타났습니다.
9회 말이 막 시작해 당황한 가희는 여러분에게 TV 화면에 나타난 [문제] T개를 빠르게 풀어 달라고 부탁했습니다.
[문제] 조건을 만족하는 수열의 개수를 구해주세요.
- 수열의 길이는 n입니다.
- 수열에 있는 모든 수는 0보다 큰 자연수입니다.
- 수열에 있는 수들의 최대공약수는 G입니다.
- 수열에 있는 수들의 최소공배수는 L입니다.
[문제]는 TV 화면에서 n G L 1줄로 표시됩니다.
입력
첫째 줄에 TV 화면에 나타난 문제의 수 T가 주어집니다.
둘째 줄부터 T+1번째 줄까지, TV 화면에 나타난 문제에 대한 정보가 n G L의 형식으로 입력됩니다. 이 수들은 공백으로 구분됩니다.
출력
각 문제에 대한 답을 109+7 (1,000,000,007)로 나눈 나머지를 한 줄에 하나씩 출력하세요.
제한
- 1 ≤ T ≤ 100
- 2 ≤ n ≤ 106
- 1 ≤ G, L ≤ 109