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 int long long
const int MOD = 1000000007;
int C[51][51];
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, K, S, T;
	cin >> N >> K >> S >> T;
	vector<int> A(N);

	for (int i = 0; i <= 50; i++) {
		C[i][0] = 1;
		C[0][i] = 1;
	}
	for (int i = 1; i <= 50; i++) {
		for (int j = 1; j <= i; j++) {
			C[i][j] = C[i - 1][j - 1];
			if (i - 1 >= j) C[i][j] += C[i - 1][j];
		}
	}
	//cerr << C[5][2] << endl;
	//cerr << C[6][3] << endl;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	vector<int> B;
	int M = 0;
	for (int j = 0; j < 19; j++) {
		if (((1 << j) & ((~S) & T))) {
			M++;
		}
	}
	for (int i = 0; i < N; i++) {
		if ((A[i] & S) == S && (A[i] | T) == T) {
			int x = 0;
			for (int j = 0; j < 19; j++) {
				if (((1 << j) & ((~S) & T))) {
					x *= 2;
					x += ((A[i] >> j) & 1);
				}
			}
			B.push_back(x);
			//cerr << x << endl;
		}
	}
	A = B;
	N = A.size();
	//cerr << M << endl;
	int res = 0;
	int sm[51];
	for (int i = 0; i <= 50; i++) {
		sm[i] = 0;
		for (int k = 1; k <= K; k++) {
			if (i >= k) {
				sm[i] += C[i][k];
			}
		}
	}
	for (int i = 0; i < (1 << M); i++) {
		map<int, int> mp;
		int bit = 0;
		for (int j = 0; j < M; j++) {
			if (i & (1 << j)) bit ^= 1;
		}
		for (int j = 0; j < N; j++) {
			mp[A[j] & i]++;
		}
		int sum = 0;
		for (const auto &x : mp) {
			sum += sm[x.second];
		}
		if (bit == 0) {
			res += sum;
		} else {
			res -= sum;
		}
	}
	cout << res << endl;
}