Background

Cool is extremely fond of Shaxian cuisine. Specifically, he loves to drag innocent people to Shaxian restaurants. Everyone is curious about how much Shaxian pays Cool for promoting their dishes, so they can coerce or entice him to treat them to KFC next door. After extensive tracking, they discovered some patterns in the payment of endorsement fees.

Problem Description

Shaxian is known for its generous endorsement fees. They have an index \( d \) when distributing these fees. They conduct \( n \) rounds of fee distribution, and in the \( i \)-th round, they distribute \( f(i) = \sum_{k|i} k^d \) amount of money.

Now, there are \( Q \) queries, each asking how much money Cool would receive from participating in the endorsement activities from round \( L_i \) to round \( R_i \) (guaranteed \( 1 \leq L_i \leq R_i \leq n \)).

Since the Shaxian restaurant on South Street is incredibly wealthy, the amount of money Cool receives needs to be taken modulo \( 10^9 + 7 \).

Input Format

The input consists of several lines.

The first line contains three integers: \( n \), \( d \), and \( 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 \) and \( R_i \).

Output Format

The output consists of \( Q \) lines.

Each line contains a single integer representing the endorsement fee Cool receives.

Sample Input and Output

Sample Input #1

10 2 2
4 5
8 10

Sample Output #1

47
306

Sample Input #2

1000 0 1
720 720

Sample Output #2

30

Notes

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 equivalent to counting the number of factors of 720.

见题面 Input 部分

见题面 Output 部分