[AdditionalFile162.zip](file://AdditionalFile162.zip?type=additional_file)

#162. 快速幂 2

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB 通过: 1665 | 提交: 5934

题目描述

这可能也是一道模板题。

给出正整数 $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 \le n \le 5 \times 10^6, 1 \le x, a_i < p, p = 99824435^2$。