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>
#define R register
#define mp make_pair
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
const int mod = 998244353;

int n, k, s, t, a[100], m, num;
ll bs[100], comb[100][100], f[100], ans, rbs[100];
vector<int> tr;

inline int addMod(int a, int b) {
	return (a += b) >= mod ? a - mod : a;
}

inline ll quickpow(ll base, ll pw) {
	ll ret = 1;
	while (pw) {
		if (pw & 1) ret = ret * base % mod;
		base = base * base % mod, pw >>= 1;
	}
	return ret;
}

template <class T>
inline void read(T &x) {
	x = 0;
	char ch = getchar(), w = 0;
	while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	x = w ? -x : x;
	return;
}

inline int popc(ll w) {
	w = (w & 0x5555555555555555) + ((w & 0xaaaaaaaaaaaaaaaa) >> 1);
	w = (w & 0x3333333333333333) + ((w & 0xcccccccccccccccc) >> 2);
	w = (w & 0x0f0f0f0f0f0f0f0f) + ((w & 0xf0f0f0f0f0f0f0f0) >> 4);
	w = (w & 0x00ff00ff00ff00ff) + ((w & 0xff00ff00ff00ff00) >> 8);
	w = (w & 0x0000ffff0000ffff) + ((w & 0xffff0000ffff0000) >> 16);
	w = (w & 0x00000000ffffffff) + ((w & 0xffffffff00000000) >> 32);
	return w;
}

void dfs(ll now, int step, int val) {
	if (!now) return;
	if (step == num) {
		ans += val * f[popc(now)];
		return;
	}
	dfs(now, step + 1, val);
	dfs(now & bs[step], step + 1, -val);
	dfs(now & rbs[step], step + 1, -val);
	return;
}

int main() {
	read(n), read(k), read(s), read(t);
	if ((s & t) != s) {
		cout << "0\n";
		return 0;
	}
	for (R int j = 0; j <= 18; ++j) {
		if ((s & (1 << j)) || (~t & (1 << j))) continue;
		tr.push_back(j), ++num;
	}
	for (R int i = 1; i <= n; ++i) {
		read(a[i]);
		if ((a[i] & s) != s || (a[i] & t) != a[i])
			continue;
		for (R int j = 0; j < num; ++j)
			if (a[i] & (1 << tr[j]))
				bs[j] |= 1ll << m;
		++m;
	}
	for (R int i = 0; i < num; ++i)
		rbs[i] = ((1ll << m) - 1) ^ bs[i];
	for (R int i = 0; i <= m; ++i) {
		comb[i][0] = 1;
		for (R int j = 1; j <= i; ++j) {
			comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
			if (j <= k) f[i] += comb[i][j];
		}
	}
	dfs((1ll << m) - 1, 0, 1);
	cout << ans << endl;
	return 0;
}