题目描述

给定一个 $n$ 次多项式 $\sum_{i=0}^{n} a_i x^i$，输出它 $m$ 次幂的 $k$ 次项系数模质数 $p$ 的值。

输入格式

从标准输入读入数据。

第一行包含两个正整数 $n$ 和 $p$，分别表示该多项式的次数和模数。

第二行包含 $n+1$ 个整数 $a_0,\dots ,a_n$，用空格分隔；其中 $a_i$ 表示该多项式的 $i​$ 次项系数。

第三行包含一个整数 $T$，表示询问组数。

接下来 $T$ 行每行两个正整数 $m$ 和 $k$ ，表示询问该多项式 $m$ 次幂的 $k$ 次项系数。

输出格式

输出到标准输出。

输出 $T$ 行。每行一个整数表示该组询问的答案。

样例

input

3 5
1 2 4 2
4
3 2
4 5
6 1
8 4

output

4
4
2
0

见附加文件（点击页面上方「附加文件」按钮下载）。

数据范围与提示

对于所有数据，保证有 $T \le 1000$， $n,p\le50$， $m,k \le10^{18}$，且 $k \le nm$，$0 \leq a_i \le p-1$（$0 \leq i \leq n$） ， $a_n \not= 0$。

子任务的详细信息如下：