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;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
int n,k,A,B,x;
ll ans,C[60][60],sum[60];
vector<int> d,e;
int yc[1<<18];
map<int,int> M;
map<int,int>::iterator it;
bool in(int s,int t) {
	return (s&t)==s&&(s|t)==t;
}
int F(int x,int i) {
	if (x&(1<<i)) return 1;
	return 0;
}
int main() {
	//printf("MLE %d\n",sizeof(dp)/1024/1024);
	//freopen("1.txt","r",stdin);
	for (int i=1;i<(1<<18);i++)
		yc[i]=yc[i-(i&(-i))]+1;
	read(n); read(k);
	read(A); read(B);
	if (!in(A,B)) { printf("0\n"); return 0; }
	
	for (int i=0;i<=n;i++) {
		C[i][0]=C[i][i]=1;
		for (int j=0;j<i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j];
		for (int j=1;j<=k;j++) sum[i]+=C[i][j];
		//printf("%d %lld\n",i,sum[i]);
	}
	
	for (int i=1;i<=n;i++) {
		read(x);
		if (in(A,x)&&in(x,B)) d.push_back(x-A);
	}
	
	
	for (int i=0;i<(1<<18);i++) if (in(i,B-A)) {
		int tmp=yc[i];
		if (tmp&1) tmp=-1;
		else tmp=1;
		
		M.clear();
		for (int j=0;j<d.size();j++)
			M[d[j]&i]++;
		
		for (it=M.begin();it!=M.end();it++)
			ans+=tmp*sum[it->second];
	}
	printf("%lld\n",ans);
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Interger overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/