Computing a Well-Known Sum

Time limit1sMemory limit1024 MB

Summary

Sum f(i)*g(i) for i from 1 to N, where f(i)=N div i and g(i)=i mod M, with N and M up to 1e9, modulo 1e9+7.

Problem

Define $f(x)$ as the quotient when $N$ is divided by $x$ , and $g(x)$ as the remainder when $x$ is divided by $M$ .

Find the remainder of the following value modulo $1\,000\,000\,007$ .

$\sum_{i=1}^N f(i)×g(i)$

The first line contains integers $N$ and $M$ , separated by a space. ( $1 \le N, M \le 10^9$ )

Print the value of the given expression modulo $1\,000\,000\,007$ .