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>
#include <vector>
#include <algorithm>

typedef long long ll;
typedef unsigned int uint;

const int MaxN = 55, MaxW = 1 << 18;

ll C[MaxN][MaxN], F[MaxN];

void init_binom(int n, int k) {
	for (int i = 0; i <= n; ++i) {
		C[i][0] = 1; F[i] = 0;
		for (int j = 1; j <= i && j <= k; ++j) {
			F[i] += C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
		}
	}
}

int buk[MaxW];

int main() {
	int n, k; uint S, T;
	scanf("%d%d%u%u", &n, &k, &S, &T);
	init_binom(n, k);
	std::vector<uint> arr;
	for (int i = 0; i < n; ++i) {
		uint x; scanf("%u", &x);
		if (S == (S & x) && T == (T | x)) arr.push_back(x);
	}
	uint M = ~S & T;
	ll ans = F[arr.size()];
	for (uint S = M; S; --S &= M) {
		for (uint x: arr) ++buk[x & S];
		ll sum = 0;
		for (uint x: arr) {
			int &t = buk[x & S];
			sum += F[t];
			t = 0;
		}
		ans += __builtin_popcount(S) & 1 ? -sum : sum;
	}
	printf("%lld\n", ans);
	return 0;
}