😀因为exgcd一次是log2N，如果直接每个a【i】求逆时间复杂度为NlogN
所以优化成
😀因为s在计算中要%p，所以s/a[i]不一定是整数，所以又要用前缀积和后缀积来处理，即s/a[i]==pre[i-1]*suf[i+1]
😀这个题目中由于时间为0.55s<1s所以读入要手写，而且前缀积应该不要直接求一个含在过程里 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=5e6+10;

ll n,p,k,a[N],y,ans;
ll pre[N],suf[N],invs; 

ll read(){
	ll x=0,flag=1; char c;//函数变量一定要初始化，否则是随机数 
	while((c=getchar())<'0'||c>'9') if(c=='-') flag=-1;
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*flag;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1; y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main(){
    n=read(); p=read(); k=read();
//    pre[0]=1;
    for(int i=1;i<=n;i++){
        a[i]=read();
//        pre[i]=pre[i-1]*a[i]%p;
    }
    suf[n+1]=1;
    for(int i=n;i>=1;i--){
    	suf[i]=suf[i+1]*a[i]%p;
	}
    exgcd(suf[1],p,invs,y);
    invs=(invs%p+p)%p;
	ll tmp=k;
    for(int i=1;i<=n;i++){
//      ans=(ans+tmp*infs%p*(pre[n]/a[i]))%p;//pre[n]计算时%p，s[n]/a[i]不一定能够整除 
//		ans=(ans+tmp*invs%p*pre[i-1]%p*suf[i+1]%p)%p;//前缀积含在过程里，不单独求 
		ans=(ans+tmp*invs%p*suf[i+1])%p;
		invs=invs*a[i]%p;
        tmp=tmp*k%p;
    }
    printf("%lld",ans);
    return 0;
}