题意：一个数列 ss，s1=am1 mod p,s2=am2 mod ps _1= a ^{m _1}\bmod p,s _2= a ^{m _2}\bmod p，满足 si=si−2α×si−1β mod p(i≥3)s _{i}=s _{i-2} ^{\alpha}\times s _{i-1} ^{\beta}\bmod p(i\ge 3)，现在已知 a,m1,m2,α,β,p(a<p≤5000,1≤α,β,i,m1,m2≤1018)a,m _{1},m _{2},\alpha,\beta,p(a<p\le 5000,1\le \alpha,\beta,i,m _{1},m _{2}\le 10 ^{18})，求 sis _{i}，K(K≤1000)K(K\le 1000) 个询问。

一道需要欧拉降幂的找循环节题目。

可以发现所有答案和过程需要对 pp 取模，而 pp 的取值范围只有 50005000，且递推式只有前两项决定。因此，数列必定存在循环节。

由于每一项模 pp 后只有 0∼49990\sim 4999 共 50005000 种可能，每一项由前两项决定，共 5000×50005000\times 5000 可能，因此循环节最长为 5000×50005000\times 5000。

所以暴力处理前 5000×50005000\times 5000 的 ss，用一个二维桶存储找循环节，记录循环节长度和最开始那一段非循环节的长度，最后直接输出就行了。

记得先预处理 0∼50000\sim 5000 的 α,β\alpha,\beta 次方，同时由于 α,β,mi\alpha,\beta,m _{i} 过大，需要欧拉降幂，降幂公式为 ax mod p=ax mod ϕ(p)+ϕ(p) mod p(x>ϕ(p))a ^{x}\bmod p=a ^{x\bmod \phi(p)+\phi (p)}\bmod p(x>\phi (p))。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=5010;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
long long a,m1,m2,alpha,beta,p;
long long s[maxn*maxn],len,pre;
long long m,al[maxn],be[maxn];
int vis[maxn][maxn];//二元桶，找循环节
long long power(long long a,long long b,long long p)
{
	long long ans=1%p;
	for(;b;b>>=1)
	{
		if(b&1)
			ans=ans*a%p;
		a=a*a%p;
	}
	return ans%p;
}
long long phi(long long x)
{
	long long sum=x;
	for(int i=2;i<=sqrt(x);i++)
		if(x%i==0)
		{
			sum=sum/i*(i-1);
			while(x%i==0)
				x/=i;
		}
	if(x>1)
		sum=sum/x*(x-1);
	return sum;
}
int main()
{
	freopen("squirrel.in","r",stdin);
	freopen("squirrel.out","w",stdout);
	scanf("%lld%lld%lld%lld%lld%lld",&a,&m1,&m2,&alpha,&beta,&p);
	long long k=phi(p)%p;
	if(m1<k)
		s[1]=power(a,m1,p);
	else
		s[1]=power(a,m1%k+k,p);
	if(m2<k)
		s[2]=power(a,m2,p);
	else
		s[2]=power(a,m2%k+k,p);
	if(alpha>=k)
		alpha=alpha%k+k;
	if(beta>=k)
		beta=beta%k+k;
	for(int i=0;i<=4999;i++)
	{
		al[i]=power(i,alpha,p);
		be[i]=power(i,beta,p);
	}
	vis[s[1]][s[2]]=1;
	for(int i=3;i<=5000*5000;i++)
	{
		s[i]=(al[s[i-2]]%p*be[s[i-1]]%p)%p;
		if(vis[s[i-1]][s[i]])
		{
			len=i-1-vis[s[i-1]][s[i]];
			pre=vis[s[i-1]][s[i]]-1;
			break;
		}
		vis[s[i-1]][s[i]]=i-1;
	}
	scanf("%lld",&m);
	for(int i=1;i<=m;i++)
	{
		long long x;
		scanf("%lld",&x);
		x=(x-pre+len-1)%len+1+pre;
		printf("%lld\n",s[x]%p);
	}
	return 0;
}