창영이의 비밀번호
시간 제한5초메모리 제한128 MB
거대한 수 n의 소인수분해가 주어질 때 lcm(a,b)=n을 만족하는 모든 쌍(a,b)에 대해 a+b의 합을 1,000,000,007로 나눈 나머지로 구합니다.
문제
창영이는 비밀번호를 만드는 함수 f를 사용한다.
양의 정수 n에 대해 f(n)은 다음과 같이 정의된다. 최소공배수가 정확히 n인, a ≤ b를 만족하는 순서 없는 쌍 (a, b)를 모두 찾아, 그 쌍들의 a + b를 전부 더한 값이다.
예를 들어 최소공배수가 6인 쌍은 (1, 6), (2, 6), (2, 3), (3, 6), (6, 6)의 5가지이므로
f(6) = (1+6) + (2+6) + (2+3) + (3+6) + (6+6) = 7 + 8 + 5 + 9 + 12 = 41
이 된다.
비밀번호를 만든 n이 주어졌을 때, 비밀번호 f(n)을 구하는 프로그램을 작성하시오. n은 매우 클 수 있으므로 소인수분해된 형태로 주어진다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. (T ≤ 500)
각 테스트 케이스의 첫째 줄에는 n의 서로 다른 소인수의 개수 C가 주어진다. (C ≤ 15)
다음 C개의 줄에는 각각 n의 소인수 Pi와 그 지수 ai가 주어진다. (2 ≤ Pi ≤ 1000, Pi는 소수, 1 ≤ ai ≤ 50) 즉, n = P1^a1 × P2^a2 × ⋯ × PC^aC 이다. 한 테스트 케이스에서 주어지는 소수는 모두 서로 다르다.
출력
각 테스트 케이스마다 f(n)을 1,000,000,007로 나눈 나머지를 한 줄에 하나씩 출력한다.