#P0031. 等比数列前n项和(困难版)
等比数列前n项和(困难版)
题目描述
等比数列是相邻两项之比为常数的数列。我们定义 为数列 的第 项,对于一个等比数列而言,我们称 为数列的第一项,即首项;任意相邻两项之比 为公比。显然,如果我们明确了一个数列的首项和公比,我们就可以唯一确定数列中的任意一项。
输入格式
输入的第一行包含空格隔开的两个整数 ( ) - 数列的首项和公比,含义如题所述。
输入的第二行包含一个数 ( ) - 代表接下来有 次询问。
接下来 行,每行输入一个整数 ( ),询问数组的前 个数之和,即 的值。
输出格式
对于每个询问,输出一行一个整数,表示对应询问的结果。由于结果可能很大,请将它对 取模后输出。
样例 #1
样例输入 #1
1 2
6
1
2
3
4
13
114514
样例输出 #1
1
3
7
15
8191
534098356