Example

Input

3 1 0 1


Output

18
#include <stdio.h>
#define P 1000000007LL
long long a[1010][1010];
long long b2[1010][1010];
long long bk[1010][1010];

long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}

long long powmod(long long a,long long b){
	if(b==0)return 1;
	if(b%2==1)return (powmod(a,b-1)*a)%P;
	long long r=powmod(a,b/2);
	return (r*r)%P;
}

int main(){
	int N;
	long long x,y,z;
	scanf("%d%lld%lld%lld",&N,&x,&y,&z);
	long long fac[1010];
	long long ifac[1010];
	fac[0]=1;
	for(int i=1;i<=N;i++)fac[i]=(fac[i-1]*i)%P;
	for(int i=0;i<=N;i++)ifac[i]=powmod(fac[i],P-2);
	long long k=x+z-y;
	if(k<0)k=-k;
	
	for(int m=1;m<=N;m++){
		for(int i=0;i*m<=N;i++){
			if(i==0)b2[m][i]=bk[m][i]=1;
			else{
				b2[m][i]=bk[m][i]=0;
				for(int j=1;j<=i;j++){
					if(gcd(j*m,k)==j){
						long long mul=fac[i-1];
						mul=(mul*ifac[i-j])%P;
						mul=(mul*powmod(m,j-1))%P;
						bk[m][i]+=(mul*bk[m][i-j])%P;
						bk[m][i]%=P;
					}
					if(gcd(j*m,2)==j){
						long long mul=fac[i-1];
						mul=(mul*ifac[i-j])%P;
						mul=(mul*powmod(m,j-1))%P;
						b2[m][i]+=(mul*b2[m][i-j])%P;
						b2[m][i]%=P;
					}
				}
			}
		}
	}
	for(int n=0;n<=N;n++){
		for(int m=0;m<=N;m++){
			if(m==0)a[n][m]=(n==0?1:0);
			else{
				a[n][m]=0;
				for(int i=0;n-i*m>=0;i++){
					long long mul=(b2[m][i]*bk[m][i])%P;
					mul=(mul*fac[n])%P;
					mul=(mul*ifac[n-i*m])%P;
					mul=(mul*ifac[i])%P;
					mul=(mul*powmod(ifac[m],i))%P;
					mul=(mul*powmod(fac[m-1],i))%P;
					a[n][m]+=(mul*a[n-i*m][m-1])%P;
					a[n][m]%=P;
				}
			}
		}
	}
	if(x>0||y>0||z>0)printf("%lld\n",a[N][N]);
	else{
		long long ans=a[N][N];
		ans=(ans*ifac[N])%P;
		ans=(ans*powmod(N,N))%P;
		printf("%lld\n",ans);
	}
}