求助大佬 45分

#include<bits/stdc++.h>
using namespace std;
#define re register
#define ll  long long
#define get getchar()
#define in inline
#define int  long long
int a[5000],s[5000][5000],p[5000],q[5000];
in int read()
{
	int t=0; char ch=get;
	while(ch<'0' || ch>'9') ch=get;
	while(ch<='9' && ch>='0') t=t*10+ch-'0', ch=get;
	return t;
} 
int fastpow(int a,int b,int p)
{ 
  int s=1;
  while(b)
  { 
  	if(b&1)
  	s=s*a%p;
  	b>>=1,a=a*a%p;
  }
  return s; 
}   
signed main()
{
 int n=read(),x=read(),mod=read(),k=read();
 for(int i=0;i<=k;i++)
 a[i]=read();
 s[0][0]=1;
 for(int i=1;i<=k;i++)
 for(int j=1;j<=i;j++)
 {  
    s[i][j]=(s[i-1][j-1]+s[i-1][j]*j%mod)%mod;
 }
 p[k]=fastpow(x+1,n-k,mod);
 for(int i=k-1;i>=0;i--)
 p[i]=p[i+1]*(x+1)%mod;
 q[0]=1;
 int ans=0,sum=0;
 for(int i=1;i<=k;i++)
 q[i]=q[i-1]*(n-i+1)%mod;
 for(int j=0;j<=k;j++)
 {
 sum=0;	
 for(int h=0;h<=j;h++)
 {
 	sum=(sum+s[j][h]%mod*q[h]%mod*p[h]%mod)%mod;
 }
  ans=(ans%mod+sum*a[j]%mod)%mod;
 }
 cout<<ans;
}