#P0031. 等比数列前n项和(困难版)

等比数列前n项和(困难版)

题目描述

等比数列是相邻两项之比为常数的数列。我们定义 aia_i 为数列 {a}\left \{ a \right \} 的第 ii 项,对于一个等比数列而言,我们称 a1a_1 为数列的第一项,即首项;任意相邻两项之比 aiai−1\frac{a_i} {a_{i-1}} 为公比。显然,如果我们明确了一个数列的首项和公比,我们就可以唯一确定数列中的任意一项。

输入格式

输入的第一行包含空格隔开的两个整数 a,ba,b ( 0≤a,b≤1090 \leq a,b \leq 10^9 ) - 数列的首项和公比,含义如题所述。

输入的第二行包含一个数 qq ( 1≤q≤1051 \leq q \leq 10^5 ) - 代表接下来有 qq 次询问。

接下来 qq 行,每行输入一个整数 nn ( 1≤n≤1091 \leq n \leq 10^9 ),询问数组的前 nn 个数之和,即 ∑i=1nai\sum_{i=1}^n a_i 的值。

输出格式

对于每个询问,输出一行一个整数,表示对应询问的结果。由于结果可能很大,请将它对 998244353998244353 取模后输出。

样例 #1

样例输入 #1

1 2
6
1
2
3
4
13
114514

样例输出 #1

1
3
7
15
8191
534098356