LCM 합

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

요약

n이 최대 10^18이고 k가 최대 30일 때, x가 1부터 n까지인 lcm(x, x+1, ..., x+k)의 합을 10^9+7로 나눈 나머지로 구합니다.

문제

임의의 수론 함수에 대해 누적합을 구하는 문제는 이제 지겹지 않은가? 형편없는 문제 출제자로서, 여기 또 하나의 문제를 준비했다.

다음 값을 구하시오.

$\sum_{x=1}^{n}\text{lcm}(x, x+1, \dots, x+k)$

답이 클 수 있으므로, $10^9 + 7$ 로 나눈 나머지를 출력하시오.

첫째 줄에 두 정수 $n$ , $k$ 가 주어진다 ( $1 \le n \le 10^{18}$ , $0 \le k \le 30$ ).

정수 하나, 즉 답을 출력한다.