P3362 Cool loves shaxian

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◕∀◕)ノヾ。

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$.

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$.

The output contains $Q$ lines. Each line contains one integer, the amount of endorsement fee Cool receives.

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