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;
namespace Base{
	# define mr make_pair
	typedef long long ll;
	typedef double db;
	const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
	const ll  infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
	template<typename T> void read(T &x){
    	x = 0; int fh = 1; double num = 1.0; char ch = getchar();
		while (!isdigit(ch)){ if (ch == '-') fh = -1; ch = getchar(); }
		while (isdigit(ch)){ x = x * 10 + ch - '0'; ch = getchar(); }
	    if (ch == '.'){
	    	ch = getchar();
	    	while (isdigit(ch)){num /= 10; x = x + num * (ch - '0'); ch = getchar();}
		}
		x = x * fh;
	}
	template<typename T> void chmax(T &x, T y){x = x < y ? y : x;}
	template<typename T> void chmin(T &x, T y){x = x > y ? y : x;}
}
using namespace Base;

const int N = 51, K = 18;
ll c[N][N], sum[N], ans;
int a[N], b[N], n, k, S, T, bi2[(1 << K) + 10], fh[(1 << K) + 10];
int main(){
	read(n); read(k);
	read(S); read(T);
	for (int i = 1; i <= n; i++) read(a[i]);
	if ((S | T) != T){
		puts("0");
		return 0;
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++)
		if (((a[i] & S) == S && (a[i] & T) == a[i]))
			a[++cnt] = a[i];
	
	n = cnt;
	for (int i = 0; i < (1 << K); i++){
		bi2[i] = bi2[i / 2] + i & 1;
		if (bi2[i] % 2 == 1) fh[i] = -1;
			else fh[i] = 1;
	}
	k--;
	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 - 1] + c[i - 1][j]);
	}
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= min(i, k); j++)
			sum[i] += c[i][j];
	for (int i = 1; i <= n; i++){
		for (int j = i + 1; j <= n; j++)
			b[j] = a[j] ^ a[i];
		for (int k = S ^ T; k >= 0; k = k > 0 ? (k - 1) & (S ^ T) : -1){
			int cnt = 0;
			for (int j = i + 1; j <= n; j++)
				if ((b[j] & k) == 0) cnt++;
			ans = ans + fh[k] * sum[cnt];
		}
	}
	cout << ans << endl;
    return 0;
}