int gauss(int A[N][N],int n)
{
	int ans = 1;
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			if(A[j][i])
			{
				for(int k=i;k<=n;k++) swap(A[i][k], A[j][k]);
				if(i!=j) ans=-ans;
				break;
			}
		}
		if(!A[i][i]) return 0;
		for(int j=i+1,iv=inv(A[i][i]);j<=n;j++)
		{
			int t=A[j][i]*iv%mod;
			for(int k=i;k<=n;k++)
				A[j][k]=(A[j][k]-t*A[i][k]%mod+mod)%mod;
		}
		ans = (ans*A[i][i]%mod+mod)%mod;
	}
	return ans;
}

int gauss(int a[N][N],int n)
{
	int res=1;
	for(int i=1; i<=n; i++)
	{
		for(int j=i+1; j<=n; j++)
		{
			while(a[j][i])
			{
				int t=a[i][i]/a[j][i];
				for(int k=i; k<=n; k++)
					a[i][k]=(a[i][k]-t*a[j][k]+mod)%mod;
				swap(a[i],a[j]);
				res=-res;
			}
		}
		res=(res*a[i][i])%mod;
	}
	return (res+mod)%mod;
}