快速求幂

题目描述

有$q$个询问，对于每个询问，输出$d^x\bmod1145141$。

输入格式

第一行输入两个数，分别表示$d,q$。

第$2 \sim q+1$行，每行输入一个数，表示$x$。

输出格式

每个询问的输出。

样例 #1

样例输入 #1

1 3
1
2
3

样例输出 #1

1
1
1

样例 #2

样例输入 #2

2 3
1
2
3

样例输出 #2

2
4
8

提示

如果你使用cin 和cout ,请加入以下两行代码且把代码里所有的endl换成'\n'：

std::ios::sync_with_stdio(0);
std::cin.tie(0);

来避免超时。

对于$20\%$的数据，0$$\le$$q$$\le$$10^3,0$$\le$$x$$\le$$10^4。

对于$50\%$的数据，0$$\le$$q$$\le$$2\times10^6,0$$\le$$x$$\le$$5 \times10^5。

对于$100\%$的数据，0$$\le$$q$$\le$$2 \times10^6,0$$\le$$x$$\le$$2 \times 10^6，0$$\le$$d$$\le$$10^4。