#3788. ZL密码锁

内存限制:128 MiB 时间限制:20 Sec

题目描述

话说考古学家ZL走进了一个山洞…………
ZL在山洞深处发现了一组密码锁,并断定这里藏着数不清的宝藏。经过一番寻找,ZL发现该密码锁上写着一串阿拉伯数字,看起来这些数字中有着一些微妙的联系。于是他动用了120分脑细胞,凭着藐视一切IMO选手的强大逻辑推理能力,找到了规律,并破解了几个密码锁。
可ZL毕竟是人,他也是会累的呀T_T
况且他的GPS显示前方还有成百上千个密码锁~!!!!
于是他把问题简化了一下,求助于身为OI神犇的你。
{============================================}
数列a[n]由如下关系式定义:
a[0]=0;
a[n]=f(a[n-1])
其中f(x)是一个正整数系数的m次多项式
对任意给定的x和y,求a[x]和a[y]的最大公约数d
令s为d模x的余数,t为d模y的余数
给定r和一个奇质数p,保证r不是p的整数倍
废话完毕,现在我们的问题是:
求方程 (rx2+sx+t) mod p = 0
有几个模p意义下的正整数解
对每个函数y=f(x)将进行T次询问

输入格式

输入文件包括T+3行
第一行一个正整数m
第二行m+1个正整数cm,…,c0,其中ci(i=m,m-1,…,0)表示f(x)中xi的系数
第三行一个正整数T,表示询问次数
以下T行每行4个正整数,分别表示x,y,r,p
//保证输入文件合法

输出格式

输出文件包含T行,每行仅输出一个整数表示方程有多少组解(模p的意义下)

样例

样例输入


			
1
2 1
1
4 8 7 3

样例输出


			
0

数据范围与提示

对于100%的数据,T<=1000,m<=10,x<y,x<=10^5,y<=10^8,p<=10^8。