Cool loves shaxian
题目背景
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 得到的带盐费。
输入输出样例
输入样例 #1
10 2 2
4 5
8 10
输出样例 #1
47
306
输入样例 #2
1000 0 1
720 720
输出样例 #2
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$ 的因数个数呢~