题目描述

这可能也是一道模板题。

给出正整数 $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$。