U495273 【模板】音速幂

音速幂是一种比快速幂还要快的快速幂。

给定正整数 $a$ 和模数 $P$ ，还有 $q$ 个数 $x_1,x_2,x_3, \ldots ,x_q$。求 $(\sum\limits_{i=1}^q a^{x_i})\bmod P$ 的值。

第一行三个正整数 $a,P,q$。 接下来为了加快读入速度，输入一个正整数 $A$，然后就不读入了。$x_1=A,x_i=x_{i-1}+i$。

输出一行一个正整数 $x$，表示 $a^b \bmod P$ 的值。

样例解释： $x_1=1,x_2=3,x_3=6,2^1+2^3+2^6=74$ |测试点编号|$a$|$q$|$P$|$A$|时间限制| | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | |$1$|$=1$|$=3.4\times10^7$|$\le10^9$|$=1$|$5s$| |$i(2 \le i \le8)$|$\le10^9$|$={i} \times10^6$|$\le10^9$|$\le10^{18}$|$2s$| |$9$|$\le10^9$|$=1.7\times10^7$|$=2$|$\le10^{18}$|$3s$| |$10$|$\le10^9$|$=3.4\times10^7$|$\le10^9$|$\le10^{18}$|$5s$| 对于所有测试点，$1 \le a \le 10^9$，$1 \le q \le 3.4 \times 10^7$，$2 \le P \le 10^9$，$1 \le A \le 10^{18}$。