快速幂（二）

已知数列 a1,a2……an和C

计算 (a1*a2*……*an)%C的结果

这里提一下广义幂的概念

设：○为一种运算且与集合V构成群，a∈V，e为○运算的幺元。

即e满足对于任意的a,有 e○a=a○e=a

我们可以记

a⁰=e

aⁿ=a^n-1○a

则有以下性质

a^n+m=aⁿ○a^m

则此时计算a关于○运算的n次幂的快速幂可以这样写

res=e;temp=a;

while(n)

{

        if(n&1)

                res=res○temp;

        temp=temp○temp;

        n>>=1;

}

return res;

然后就像a^b=a*a*a*a*a… 是关于乘法的幂运算，又因为1*a=a*1=a,所以乘法幺元e就是1，带入上面的程序就可以得到最常见的乘法快速幂

同理，a*b=a+a+a+a……,其实就是关于加法的幂运算，至于加法的幺元，自己找。找不到就不要来见我

有多组测试数据

每组数据第一行是两个整数 n，C

接下来一行有n个整数，代表a1,a2,……，an；

其中

2<=n<=100

1<ai,C<2^60

数据约200组

输出对应的计算结果，每个结果占一行

2 123456789987654321
123456789123456789 987654321123456789

54869682945130317