class Combination(): def __init__(self, N, MOD): self.factorial=[1]*(N+1) self.fact_inv=[1]*(N+1) self.MOD=MOD for k in range(1,N): self.factorial[k+1]=(self.factorial[k]*(k+1))%MOD self.fact_inv[N]=pow(self.factorial[N],MOD-2,MOD) for k in range(N,0,-1): self.fact_inv[k-1]=(self.fact_inv[k]*k)%MOD def cmb(self, n, r): if n<0 or r<0 or n0: res=res*C.cmb(x_plus+a-1,a)%mod if b>0: res=res*C.cmb(x_minus+b-1,b)%mod if c>0: res=res*C.cmb(y_plus+c-1,c)%mod if d>0: res=res*C.cmb(y_minus+d-1,d)%mod ans+=res print(ans%mod)