记录编号	612727	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[统一省选 2020]组合数问题	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	0.617 s
提交时间	2026-02-25 19:46:10	内存使用	7.46 MiB

#include<iostream>
using namespace std;

const int MAXM = 1005;
#define ll long long
int n, x, p, m;
ll a[MAXM], b[MAXM];
ll S[MAXM][MAXM];

ll qpow(ll a, ll b){
	ll res = 1;
	a %= p;
	while(b){
		if(b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

int main(){
	
	cin.tie(0) -> ios::sync_with_stdio(0);
	
	cin >> n >> x >> p >> m;
	
	for(int i = 0;i <= m;i ++) cin >> a[i];
	S[0][0] = 1;
	for(int i = 1;i <= m;i ++){
		for(int j = 1;j <= i;j ++){
			S[i][j] = (S[i - 1][j - 1] + j * S[i - 1][j]) % p;
		}
	}
	
	for(int j = 0;j <= m;j ++){
		for(int i = 0;i <= m;i ++){
			(b[j] += ((a[i] * S[i][j]) % p)) %= p;
		}
	}
	
	ll mi = 1, ans = 0, xi = 1;
	for(int i = 0;i <= m;i ++){
		ll del = b[i];
		(del *= mi) %= p;
		(del *= xi) %= p;
		(del *= qpow(x + 1, n - i)) %= p;
		(ans += del) %= p;
//		(ans += (b[i] * mi * qpow(x, i) * qpow(x + 1, n - i))) %= p;
		(mi *= (n - i)) %= p;
		(xi *= x) %= p;
	}
	cout << (ans + p) % p << '\n';
	return 0;
}