시간 제한메모리 제한제출정답맞힌 사람정답 비율
7 초 512 MB3518736.842%

문제

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.

예제 입력 1

10 3

예제 출력 1

18936

예제 입력 2

10000 6

예제 출력 2

43482752

예제 입력 3

1000000000 15

예제 출력 3

688102997