题目背景

Cool 非常非常喜欢吃沙县,确切地说,他非常非常把各种无辜群众拉到沙县去吃饭(╯‵□′)╯(┻━┻。大家都非常非常想知道沙县到底给了 Cool 多少钱带盐沙县小吃,以便未来威逼利诱 Cool 来请客吃隔壁的 KFC。经过多方追踪,大家发现了带盐费发放的某一些规律ヾ(o◕∀◕)ノヾ。

题目描述

沙县发放带盐费以壕著称。这家沙县发放带盐费时有个指数 $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$ 取模得到的答案。

输入格式

输入包含若干行。

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

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

输出格式

输出包含 $Q$ 行。

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

10 2 2
4 5
8 10

47
306

1000 0 1
720 720

30

提示

样例 $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$ 的因数个数呢~