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;

#define LL long long

int n, m, k, S, T, c;
int a[55];
int bc[1 << 19], cnt[1 << 19];
LL C[55][55], coef[55];

int main()
{
	scanf("%d %d %d %d", &m, &k, &S, &T);
	
	if((S | T) != T) return puts("0"), 0;

	for(int i = 1; i <= m; i++)
	{
		int x, v = 0; 
		bool fk = true;
		scanf("%d", &x);
		for(int j = 0; j < 18; j++)
		{
			if((S >> j & 1) && !(x & 1)) fk = false;
			if(!(T >> j & 1) && (x & 1)) fk = false;
			if(!(S >> j & 1) && (T >> j & 1)) v = (v << 1) | (x & 1);
			x >>= 1;
		}
		if(fk) a[++ n] = v;
	}
	
	for(int i = 0; i < 18; i++)
		if(!(S >> i & 1) && (T >> i & 1)) c ++;
	
	S = 0, T = (1 << c) - 1;
	for(int i = 0; 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 j = 0; j < k; j++) coef[i] += C[i][j];
	}

	for(int i = 1; i <= T; i++) bc[i] = bc[i >> 1] + (i & 1);

	LL ans = 0;
	for(int i = 1; i <= n; i++)
	{
		for(int s = 0; s <= T; s++) cnt[s] = 0;
		for(int j = i + 1; j <= n; j++) cnt[ a[i] ^ a[j] ] ++;
		
		for(int j = 0; j < c; j++)
			for(int s = 0; s <= T; s++)
				if(s >> j & 1) cnt[s] += cnt[s ^ (1 << j)];

		for(int s = 0; s <= T; s++)
			if(bc[T ^ s] & 1) ans -= coef[ cnt[s] ];
			else ans += coef[ cnt[s] ];
	}

	printf("%lld\n", ans);
	return 0;
}