#577. 「LibreOJ NOI Round #2」简单算术

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: zx2003

题目描述

给定一个 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 行。每行一个整数表示该组询问的答案。

样例

样例输入 1

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

样例输出 1

4
4
2
0

样例 2

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

数据范围与提示

对于所有数据,保证有 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

子任务的详细信息如下:

测试点编号 n= p= m\le
1 50 3 10
2 5
3 7 2\times10^4
4 11
5 13
6 17 10^5
7 1 2 10^{18}
8 20
9
10 3
11 5
12 7
13 50 2
14
15
16 19
17 31
18 37
19 43
20 47