#162. 快速幂 2

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: foreverlasting

题目描述

这可能也是一道模板题。

给出正整数 x n 个正整数 a_i ,求 x^{a_i} \bmod p

输入格式

第一行,两个正整数 x n

第二行, n 个正整数 a_i

输出格式

一行 n 个正整数,分别表示 x^{a_i} \bmod p

样例

样例输入

2 3
1 2 3

样例输出

2 4 8

数据范围与提示

对于 100\% 的数据, 1\leq n\leq 5\times 10^6,1\leq x,a_i<p,p=99824435\color{red}2