LCM Sum

Time limit7sMemory limit512 MB

Summary

Given n up to 10^18 and k up to 30, compute the sum of lcm(x, x+1, ..., x+k) for x from 1 to n, modulo 10^9+7.

Level: Hard9 of 10
Topics: Number theory, Math, Combinatorics
Solved: No attempts yet

Problem

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

Compute

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

The answer can be large, so output it modulo $10^9 + 7$ .

Input

The first line contains two integers $n$ and $k$ ( $1 \le n \le 10^{18}$ , $0 \le k \le 30$ ).

Output

Output one integer: the answer.

Examples3

Example 1
Input
```
10 3
```
Expected output
```
18936
```
Example 2
Input
```
10000 6
```
Expected output
```
43482752
```
Example 3
Input
```
1000000000 15
```
Expected output
```
688102997
```