Description

沙县发放带盐费以壕著称。这家沙县发放带盐费时有个指数 $d$。他会发放 $n$ 轮带盐费，在第 $i$ 轮中，都会发放 $f(i) = \sum_{k|i} k^d (i \leq n)$ 这么多的钱。

现在大家有了 $Q$ 个问题，每个问题都形如 Cool 参加从第 $L_i$ 轮到第 $R_i$ 轮的带盐活动，将能获得多少钱。（保证 $1 \leq L_i \leq R_i \leq n$）

由于开在南大街的沙县小吃不是一般的有钱啊，所以呢，我们要计算的是 Cool 收到的钱对 $10^ 9 + 7$ 取模得到的答案。

Input Format

输入包含若干行。

第一行，三个整数，$n, d, Q$。（$n\leq 10^7$，$d\leq 10^{18}$，$q\leq 5\times 10^4$。

接下来的 $Q$ 行,每行两个整数 $L_i, R_i$。

Output Format

输出包含 $Q$ 行。

每行一个整数，表示 Cool 得到的带盐费。

10 2 2
4 5
8 10

47
306

1000 0 1
720 720

30

Hint

样例 $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$

样例 $2$：

就相当于在数 $720$ 的因数个数呢~