Salty Fee Distribution

In this problem, we consider a unique distribution of money over n rounds. There is a parameter \(d\) and in each round \(i\) (with \(1 \le i \le n\)), the amount of money given is defined as:

\(f(i) = \sum_{k|i} k^d\)

You will be given \(Q\) queries. Each query asks for the total amount of money received in rounds from \(L\) to \(R\) (inclusive). Since the amounts can be very large, you are required to output the result modulo \(10^9+7\).

Input: The first line contains three integers \(n\), \(Q\), and \(d\). Then \(Q\) lines follow; each contains two integers \(L\) and \(R\) (\(1 \le L \le R \le n\)).

Output: For each query, output the required sum modulo \(10^9+7\>.

inputFormat

The first line of input contains three space-separated integers: n (the number of rounds), Q (the number of queries), and d (the exponent parameter). The next Q lines each contain two space-separated integers L and R, representing a query asking for the total money received from round L to round R.

outputFormat

For each query, print a single line containing one integer — the total amount of money received in the corresponding rounds, taken modulo \(10^9+7\).

sample

10 2 1
1 5
6 10

21
66