[TJOI2015]棋盘

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define uint unsigned int
using namespace std;
const int M=1<<6;
struct Mx{
	uint a[M][M];
	uint* operator[] (int x) {return a[x];}
}a,a_,emp;
int n,m,p,k,N;
uint ans;
int b[3];
int A[M][M],f[3][M];
bool use[M];
Mx operator* (Mx a,Mx b)
{
	Mx c=emp;
	for(int i=0;i<N;++i)
	  for(int j=0;j<N;++j)
	    for(int k=0;k<N;++k)
	      c[i][j]+=b[i][k]*a[k][j];
	return c;
}
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
Mx Pow(Mx a,int b)
{
	Mx ans=emp;
	for(int i=0;i<N;++i)
	  ans[i][i]=1;
	for(;b;b>>=1,a=a*a)
	  if(b&1) ans=ans*a;
	return ans;
}
bool check(int x)
{
	for(int i=0;i<m;++i)
	  if(x&(1<<i)) if(i<=k) {if(x&(b[1]-(1<<k)>>(k-i))) return 0;}
	  else if(x&(b[1]-(1<<k)<<(i-k))) return 0;
	return 1;
}
int main()
{
	n=read(),m=read(),p=read(),k=read(),N=1<<m;
	for(int i=0;i<=2;++i)
	  for(int j=0;j<p;++j)
	    A[i][j]=read(),b[i]|=A[i][j]*(1<<j);
	for(int i=0;i<N;++i)
	  if(use[i]=check(i)) for(int j=0;j<m;++j)
	    if(i&(1<<j)) if(j<=k) f[0][i]|=(b[0]>>(k-j)),f[1][i]|=(b[1]>>(k-j)),f[2][i]|=(b[2]>>(k-j));
	    else f[0][i]|=(b[0]<<(j-k)),f[1][i]|=(b[1]<<(j-k)),f[2][i]|=(b[2]<<(j-k));
	for(int i=0;i<N;a_[i][0]=1,++i)
	  if(use[i]) for(int j=0;j<N;++j)
	    if(use[j]&&!(f[2][i]&j)&&!(i&f[0][j])) a[j][i]=1;
	a_=Pow(a,n);
	for(int i=0;i<N;++i)
	  ans+=a_[i][0];
	return printf("%u",ans),0;
}