Description

Shaxian is famous for being lavish when paying endorsement (dàiyán) fees. When this Shaxian pays endorsement fees, it uses an exponent $d$. It will pay fees for $n$ rounds. In the $i$-th round, it pays $f(i) = \sum_{k|i} k^d (i \leq n)$ money.

Now there are $Q$ queries. Each query asks: if Cool participates from round $L_i$ to round $R_i$, how much money will he receive? (It is guaranteed that $1 \leq L_i \leq R_i \leq n$.)

Since the Shaxian Snacks on South Street is insanely rich, we need to compute the answer modulo $10^ 9 + 7$.

Input Format

The input contains multiple lines.

The first line contains three integers, $n, d, Q$ ($n\leq 10^7$, $d\leq 10^{18}$, $Q\leq 5\times 10^4$).

The next $Q$ lines each contain two integers $L_i, R_i$.

Output Format

The output contains $Q$ lines.

Each line contains one integer, the amount of endorsement fee Cool receives.

10 2 2
4 5
8 10

47
306

1000 0 1
720 720

30

Hint

Sample 1:

$f(4) = 1^2 + 2^2 + 4^2 = 21$.

$f(5) =1^2+5^2= 26$.

$f(8) + f(9) + f (10) = 85 + 91 + 130= 306$.

Sample 2:

This is essentially the number of divisors of the number $720$~.

Translated by ChatGPT 5