Example

Input

3 1 0 1


Output

18
#include<stdio.h>
#include<algorithm>
using namespace std;
long long mod=1000000007;
int inv[1100];
int fact[1100];
int factinv[1100];
int pow[1100][1100];
int factpow[1100][1100];
int invpow[1100][1100];
long long dp[1100][1100];
long long dp2[1100][1100];
long long dp3[1100][1100];
int finvpow[1100][1100];
long long gcd(long long a,long long b){
	while(a){
		b%=a;
		long long c=a;a=b;b=c;
	}
	return b;
}
long long ABS(long long a){return max(a,-a);}
int main(){
	inv[1]=1;
	for(int i=2;i<1100;i++)inv[i]=(mod-(mod/i)*(inv[mod%i])%mod)%mod;
	fact[0]=factinv[0]=1;
	for(int i=1;i<1100;i++){
		fact[i]=(long long)fact[i-1]*i%mod;
		factinv[i]=(long long)factinv[i-1]*inv[i]%mod;
	}
	for(int i=0;i<1100;i++){
		pow[i][0]=factpow[i][0]=invpow[i][0]=finvpow[i][0]=1;
		for(int j=1;j<1100;j++){
			pow[i][j]=(long long)pow[i][j-1]*i%mod;
			factpow[i][j]=(long long)factpow[i][j-1]*fact[i]%mod;
			invpow[i][j]=(long long)invpow[i][j-1]*inv[i]%mod;
			finvpow[i][j]=(long long)finvpow[i][j-1]*factinv[i]%mod;
		}
	}
	int a;
	long long b,c,d;
	scanf("%d%lld%lld%lld",&a,&b,&c,&d);
	long long t=ABS(b-c+d);
	if(b==0&&c==0&&d==0){
		long long ret=0;
		for(int i=0;i*2<=a;i++){
			ret=(ret+(long long)fact[a]*invpow[2][i]%mod*factinv[i]%mod*factinv[a-i*2]%mod)%mod;
		}
		printf("%lld\n",ret*pow[a][a]%mod);
		return 0;
	}
	for(int i=1;i<=a;i++){
		dp3[i][0]=1;
		for(int j=1;j<=a/i;j++){
			if(t%j||gcd(t/j,i)!=1)continue;
			for(int k=a/i;k>=0;k--){
				for(int l=1;k+l*j<=a/i;l++){
					dp3[i][k+l*j]=(dp3[i][k+l*j]+(long long)dp3[i][k]*finvpow[j][l]%mod*factinv[l]%mod*factpow[j-1][l]%mod*invpow[i][l])%mod;
				}
			}
		}
	}
	for(int i=1;i<=a;i++){
		if(i%2==0){
			for(int j=0;j<=a/i;j++){
				if(j%2)continue;
				dp2[i][j]=(long long)fact[i*j]*factinv[j/2]%mod*invpow[2][j/2]%mod*finvpow[i][j]%mod*pow[i][j/2]%mod;
			}
			continue;
		}
		for(int j=0;j<=a/i;j++){
			for(int k=0;k*2<=j;k++){
				dp2[i][j]=(dp2[i][j]+(long long)fact[i*j]*factinv[j-k*2]%mod*factinv[k]%mod*invpow[2][k]%mod*pow[i][k]%mod*finvpow[i][j])%mod;
			}
		}
	}
	dp[0][0]=1;
	for(int i=0;i<=a;i++){
		for(int j=0;j<a;j++){
			if(!dp[i][j])continue;
			int v=j+1;
			for(int k=0;i+k<=a;k+=v){
				dp[i+k][v]=(dp[i+k][v]+(long long)dp[i][j]*dp2[v][k/v]%mod*dp3[v][k/v]%mod*fact[k/v]%mod*factpow[v][k/v]%mod*fact[a-i]%mod*factinv[a-i-k]%mod*factinv[k])%mod;
			}
		}
	}
/*	for(int i=1;i<=a;i++){
		for(int j=0;j<=a/i;j++){
			printf("%lld ",dp2[i][j]*dp3[i][j]%mod*fact[j]%mod*factpow[i][j]%mod);
		}
		printf("\n");
	}
	for(int i=0;i<=a;i++){
		for(int j=0;j<=a;j++)printf("%lld ",dp[j][i]);
		printf("\n");
	}*/
	printf("%lld\n",dp[a][a]%mod);
}