피보나치 수의 최대공약수의 합처럼 보이지만...

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

요약

n과 k가 주어질 때 1부터 n까지 모든 쌍 (i, j)에 대해 gcd(i, j)의 k제곱과 gcd(F_i, F_j)를 곱한 값의 합을 1,000,000,007로 나눈 나머지로 구합니다.

문제

피보나치 수는 다음 규칙으로 만들어지는 수열입니다.

$\begin{align*} F_{1} &= 1 \\ F_{2} &= 1 \\ F_{n+2} &= F_{n+1} + F_{n} \end{align*}$

처음 몇 개의 항은 다음과 같습니다.

1, 1, 2, 3, 5, 8, 13 ...

다음 합을 구해봅시다.

$\sum_{i=1}^{n}\sum_{j=1}^{n} (\gcd(i, j))^{k}\gcd(F_{i}, F_{j})$

이때 gcd는 최대공약수를 의미합니다. 답이 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력합시다.

첫 번째 줄에 두 정수 $n$ 과 $k$ 가 주어집니다. ( $1 \le n \le 10^{9}$ , $0 \le k \le 4000$ )

첫 번째 줄에 구하는 합을 1,000,000,007로 나눈 나머지를 출력합니다.