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<cstdio>
long long c[55][55];
int a[55], b[55];
int andBit[20], orBit[20];
int curBit[20];
long long count0[1<<20], count1[1<<20];
long long sign[1<<20];
long long sum[55][55];

long long getC(int n,int m){
	if(m>n || m<0) return 0;
	else return c[n][m];
}

void preWork(int n){
	c[0][0] = 1;
	for(int i = 1; i <= n; i++){
		c[i][0] = 1;
		for(int j = 1; j <= i; j++){
			c[i][j] = c[i-1][j]+c[i-1][j-1];
		}
	}
	for(int i = 0; i < (1<<18); i++){
		sign[i] = 1;
		int mask = i;
		for(int j = 0; j < 18; j++){
			if(mask%2) sign[i] *= -1;
			mask /= 2;
		}
	}
	for(int i = 0; i <= n; i++){
		sum[i][0] = 0;
		for(int j = 1; j <= n; j++){
			sum[i][j] = sum[i][j-1]+getC(i,j);
		}
	}
}

int translate(int n){
	int count = 0;
	for(int i = 1; i <= n; i++){
		int u = a[i], size = -1;
		int ok = 1;
		for(int j = 0; j < 18; j++){
			if(andBit[j]){
				if(u%2==0){ 
					ok = 0; 
					break;
				}
			}
			else if(orBit[j]==0){
				if(u%2!=0){
					ok = 0;
					break;
				}
			}
			else curBit[++size] = u%2;
			u /= 2;
		}
		if(ok){
			int add = 0;
			for(int j = size; j >= 0; j--) add = add*2+curBit[j];
			b[++count] = add;
		}
	}
	return count;
}

void calCount(int n,int bitCnt){
	for(int i = 0; i < (1<<bitCnt); i++){
		count0[i] = count1[i] = 0;
		for(int j = 1; j <= n; j++){
			count0[i] *= 2, count1[i] *= 2;
			if((b[j]&i)==0) count0[i]++;
			if((b[j]&i)==i) count1[i]++;
		}
	}
}

int popCount(long long u){
	return __builtin_popcountll(u);
}

int main(){
	preWork(50);
	int n,k,s,t;
	scanf("%d%d%d%d",&n,&k,&s,&t);
	for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
	if((s&t)!=s) printf("0\n");
	else{
		int bitCnt = 0;
		for(int i = 0; i < 18; i++){
			andBit[i] = s%2, orBit[i] = t%2;
			if(andBit[i]==0 && orBit[i]!=0) bitCnt++;
			s /= 2, t /= 2;
		}
		int size = translate(n);
		/*printf("bitCnt = %d, size = %d\n",bitCnt,size);
		for(int i = 1; i <= size; i++) printf("%d ",b[i]);
		printf("\n");*/
		calCount(size,bitCnt);
		long long ans = 0;
		for(int i = 0; i < (1<<bitCnt); i++){
			for(int j = i; ; j = i&(j-1)){
				long long have = popCount(count0[i^j]&count1[j]);
				ans += sign[i]*sum[have][k];
				if(j==0) break;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}