시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 22 13 4 50.000%

문제

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

$\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로 나눈 나머지를 출력합시다.

입력

첫번째 줄에 두 개의 정수 nk가 주어집니다. (1 ≤ n ≤ 109, 0 ≤ k ≤ 4000)

출력

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

예제 입력 1

6 0

예제 출력 1

52

예제 입력 2

6 3

예제 출력 2

2786

예제 입력 3

3392 966

예제 출력 3

220437023

예제 입력 4

247156804 3939

예제 출력 4

421403669

출처

채점

  • 소스 코드의 크기는 20000B을 넘을 수 없다.