Problem: Given are N pairwise distinct non-negative integers A_1,A_2,\ldots,A_N. Find the number of ways to choose a set of between 1 and K numbers (inclusive) from the given numbers so that the following two conditions are satisfied:

* The bitwise AND of the chosen numbers is S.
* The bitwise OR of the chosen numbers is T.

Constraints

* 1 \leq N \leq 50
* 1 \leq K \leq N
* 0 \leq A_i < 2^{18}
* 0 \leq S < 2^{18}
* 0 \leq T < 2^{18}
* A_i \neq A_j (1 \leq i < j \leq N)

Input

Input is given from Standard Input in the following format:


N K S T
A_1 A_2 ... A_N


Output

Print the answer.

Examples

Input

3 3 0 3
1 2 3


Output

2


Input

5 3 1 7
3 4 9 1 5


Output

2


Input

5 4 0 15
3 4 9 1 5


Output

3

Solution (in CPP):

Solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
#define N 60

LL n,m,p,s,t,k,c[N][N],a[N],b[N],C[N],f[1<<18],ans;


void fmt(LL f[]){
	for (LL i=0;i<k;++i){
		for (LL j=0;j<1<<k;j+=1<<(i+1)){
			LL *f0=f+j,*f1=f+j+(1<<i);
			for (LL t=0;t<1<<i;++t) f1[t]+=f0[t];
		}
	}
}

LL bit(LL x,LL k){
	return x>>k&1;
}

int main(){
	scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
	if ((s|t)!=t){puts("0"); return 0;}
	for (LL i=0;i<18;++i){
		if (bit(s,i)!=bit(t,i)){
			b[k++]=i;
		}
	}
	for (LL i=1;i<=n;++i){
		LL x; scanf("%lld",&x);
		if ((x&s)!=s) continue;
		if ((x|t)!=t) continue;
		++p;
		for (LL j=0;j<k;++j){
			a[p]|=bit(x,b[j])<<j;
		}
	}
	for (LL i=0;i<=n;++i){
		c[i][0]=1;
		for (LL j=1;j<=i;++j) c[i][j]=c[i-1][j]+c[i-1][j-1];
	}
	for (LL i=0;i<=n;++i){
		for (LL j=0;j<m;++j) C[i]+=c[i][j];
	}
	for (LL i=1;i<=p;++i){
		memset(f,0,sizeof f);
		for (LL j=i+1;j<=p;++j){
			++f[a[j]^a[i]];
		}
		fmt(f);
		for (LL j=0;j<1<<k;++j){
			ans+=C[f[j]]*((k-__builtin_popcount(j))&1?-1:1);
		}
	}
	printf("%lld\n",ans);
	
	return 0;
}