1 问题
题面描述
国际象棋是很久以前由一个印度人 Shashi 发明的，当他把该发明献给国王的时候，国王很高兴，就许诺可以给这个发明人任何他想要的奖赏。Shashi 要求以这种方式给他一些粮食：棋盘的第 1 个方格里只放 1 粒麦粒，第 2 格 q 个,第 3 格 q^2^ 个,第 4 格 q^3^ 个……，直到 n 个格子全部放满。这个奖赏最终会是什么样子的呢？Shashi 已经有算法了，请你算一算吧。
当然 Shashi 并不关心具体的数有多少了，他有一个检验你的答案是否与他心意相通的办法:把你求出的答案对 100000007 取模看看和 Shashi 算的是否一样就行了。
输入描述
本题输入具有多组样例。
第一行为一个数 t (1 ≤ t ≤ 500)，代表测试数据的组数。
之后的 t 行，每行两个数 q, n (1 ≤ q, n ≤ 10^18^)，含义见题目描述。
输出描述
输出共 t 行，每行一个数，为你算的答案。 友情提醒：你算的答案应该比 100000007 小。
样例描述
样例输入：
3
2 1
2 2
2 3样例输出：
1
3
7样例解释
对于样例：
- q = 2, n = 1 时仅有1个麦粒
- q = 2, n = 2 时有 1 + 2 = 3 个麦粒
- q = 2, n = 3 时有 1 + 2 + 2^2^ = 7 个麦粒
作者｜cugbacm
单位｜中国地质大学（北京）
代码长度限制｜16 KB
时间限制｜1000 ms
内存限制｜256 MB
2 分析
2.1 数学抽象
该问题本质为等比数列求和问题， 为首项， 为公比， 为项数。 需要注意：
- 每次输入的 , 可能不同；
- , 的范围超过 int32，需要用 int64 来存储；
- 结果要对 取模；
- 计算过程中涉及到大数乘法，直接用
*运算符会造成数据溢出，需要用自己设计的大数乘法模运算作为替代。