Background

Cool really, really loves eating at Shaxian. To be precise, he really, really likes dragging all kinds of unsuspecting folks to Shaxian for meals (╯‵□′)╯(┻━┻. Everyone is dying to know how much money Shaxian has paid Cool to "endorse" (dàiyán) Shaxian Snacks, so that in the future they can threaten and cajole Cool into treating them to the KFC next door. After much tracking, people discovered some patterns in how the endorsement fees are paid out ヾ(o◕∀◕)ノヾ。

Problem 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