GCD 곱

시간 제한5초메모리 제한512 MB

요약

1 이상 N 이하의 i와 1 이상 M 이하의 j 모든 쌍에 대해 gcd(i, j)를 곱한 값을 10^9+7로 나눈 나머지를 구한다. N과 M은 최대 1500만이다.

문제

$N$ 과 $M$ 이 주어진다. $1$ 이상 $N$ 이하의 모든 $i$ 와 $1$ 이상 $M$ 이하의 모든 $j$ 에 대해 최대공약수 $\gcd(i, j)$ 를 전부 곱한 값을 구하는 프로그램을 작성하시오.

$\prod_{i=1}^{N}\prod_{j=1}^{M}\gcd(i, j)$

첫째 줄에 $N$ 과 $M$ 이 공백으로 구분되어 주어진다. ( $1 \le N, M \le 15{,}000{,}000$ )

첫째 줄에 곱을 $10^9 + 7$ 로 나눈 나머지를 출력한다.