思路：

这题的入手点在于枚举有多少个一。由于两个一不能相邻，所以最多只会有 $\left\lfloor\tfrac{n + 1}{2}\right\rfloor$ 个一。考虑序列中有 $i$ 个一的情况。此时有 $n - i$ 个零，把这 $i$ 个一插入到 $n - i$ 个零组成的空隙中，有 $C_{n - i + 1} ^ i$ 种方案。每种方案的价值为 $i^b \times (n - i) ^ a$。所以答案就是 $\sum\limits_{i = 0} ^ {\left\lfloor\tfrac{n + 1}{2}\right\rfloor} C_{n - i + 1} ^ i \times (n - i) ^ a \times i ^ b$。由于 $n\le 10^7$，所以暴力算是会超时的，考虑优化快速幂。由于只用求一个数的 $a$ 和 $b$ 次方。所以我们可以对每一个 $i \le 10^7$ 质因数分解，则 $pwa_i = pwa_p \times pwa_{\tfrac{i}{p}}$，$pwb_i = pwb_p \times pwb_{\tfrac{i}{p}}$。这样一来，我们就只用求质数的 $a$ 次方和 $b$ 次方。把时间复杂度降到了 $O( n)$，可以通过。

AC 代码：

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1e7+5;
int n,a,b,m,fac[N],inv[N];
int qpow(int a,int b){
	int s=1;
	while(b){
		if(b&1) s=1ll*s*a%m;
		a=1ll*a*a%m,b>>=1;
	}
	return s;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>a>>b>>m;
	fac[0]=1;
	for(int i=1;i<=n+1;++i) fac[i]=1ll*fac[i-1]*i%m;
	inv[n+1]=qpow(fac[n+1],m-2);
	for(int i=n;~i;--i) inv[i]=1ll*inv[i+1]*(i+1)%m;
	int ans=0;
	for(int i=0;i<=n;++i) if(i<=n-(i-1)) ans=(ans+1ll*fac[n-(i-1)]*inv[i]%m*inv[n-(i-1)-i]%m*qpow(n-i,a)%m*qpow(i,b))%m;
	cout<<ans<<endl;
	return 0;
}