给定一个 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 行。每行一个整数表示该组询问的答案。
3 5 1 2 4 2 4 3 2 4 5 6 1 8 4
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 。
子任务的详细信息如下：
