[Login|Register]
Problems

Status

Rank

Problem 1426
这是最后一题普通版
Time Limit: 2000ms
Memory Limit: 65536kb
Description
红红要过生日了,非常想喝咖啡,但是又不想去遥远的星巴克,于是决定自己亲自磨咖啡豆。于是找到了珍藏多年的咖啡豆,但是竟然发现这些咖啡豆都发霉了,于是他把这些豆子排成一排,1、2、3… n,每个豆子的“霉度”为 i ^ k,i 为咖啡豆的序号,k 为一个与日期相关的正整数,现在他想知道从 l 到 r 所有豆子的霉度和,但是他的数学水平有些不够,你能帮帮他么?
Input

第一行三个整数 n <= 100000,k <= 10^18,q <= 100000。

n,k为题目中所说,q 为红红要问你的询问数。

下面共q行,每行两个整数 l ,r 表示一次询问。

Output

共 q 行,第i行输出第i个询问的答案。

可能答案过大,答案对10 ^ 9 + 7 取模

Sample Input
5 2 3

1 4

2 2

3 5
Sample Output
30
4
50
Source
zc
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 0.9ms with 1 query(s).