LCM Sum

1부터 n까지의 각 x에 대해 x부터 x+k까지 연속한 정수들의 최소공배수를 구해 모두 더한 값을 1e9+7로 나눈 나머지를 출력한다.

어려움8정수론수학누적 합아직 제출이 없습니다시간 제한7초메모리 제한512 MB

문제 설명

예제3

문제

Are you sick of solving problems like computing the prefix sum of a random number theory function? As a terrible problem writer, here I present another one for you.

Compute

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

The answer can be large, so output it modulo 109 + 7.

입력

The first line contains two integers n, k (1 ≤ n ≤ 1018, 0 ≤ k ≤ 30).

출력

Output one integer: the answer.