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

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

\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 ≤ n ≤ 109, 0 ≤ k ≤ 100,000)

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