跳跃的旋律

题号：NC25856
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

ssy最可爱了！我会爱你3000遍的

——水宝宝

空中有几颗星星，水宝宝正在仰望着,幻想着与ssy......

为了省事，我们把天空看成一条从1开始的长度为n的数轴，数轴上的每个整数点

都有一个值，表示这个点的星星的数量，现在，水宝宝为了给ssy一个惊喜，想知道对于给定的x,y,

$\prod_{i=0}^k a_{x+i\cdot y}$ 是多少呢？ (x+ky<=n)(k>=0)

为了防止数字太大，你需要把答案mod 20180718

注:本系列题不按难度排序哦

第一行一个数表示n，询问次数m

接下来一行n个数，表示数轴上每个点星星的数量

接下来m行，每行一个x，y，表示询问

m行，对于每一组x,y，输出 (x+ky<=n)(k>=0)

示例1

复制

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

复制

12
40
20160

样例解释:第一组数据，答案为a[1]*a[1+3]=12

第二组数据，答案为a[2]*a[2+4]=a[2]*a[6]=5*8=40

第三组数据有更好的解法，可惜这里空间太小，写不下了QAQ

对于100%的数据,n,m<=500000，a[i]<=1000000