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 <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, K, S, T;
vector<int> A;

i64 dp[2][55];
i64 C[55][55];

int main()
{
	C[0][0] = 1;
	for (int i = 1; i <= 50; ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= 50; ++j) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
	}
	scanf("%d%d%d%d", &N, &K, &S, &T);
	if ((S & T) != S) {
		puts("0");
		return 0;
	}
	vector<int> rels;
	for (int i = 0; i < 18; ++i) {
		if (((S >> i) & 1) == 0 && ((T >> i) & 1) != 0) {
			rels.push_back(i);
		}
	}
	for (int i = 0; i < N; ++i) {
		int x;
		scanf("%d", &x);
		if ((x & S) == S && (x & T) == x) {
			int x2 = 0;
			for (int j = 0; j < rels.size(); ++j) {
				x2 |= ((x >> rels[j]) & 1) << j;
			}
			A.push_back(x2);
		}
	}

	int B = rels.size();
	N = A.size();

	//printf("%d\n", N);
	//for (int i = 0; i < N; ++i) printf("%d ", A[i]);
	//puts("");
	i64 ret = 0;
	for (int m = 0; m < (1 << B); ++m) {
		map<int, int> grps;
		for (int i = 0; i < N; ++i) {
			if (grps.count(A[i] & m) == 0) grps[A[i] & m] = 1;
			else grps[A[i] & m] += 1;
		}
		/*
		int t = 0;
		for (int i = 0; i <= K; ++i) {
			dp[t][i] = 0;
		}
		dp[t][0] = 1;
		for (auto e : grps) {
			int w = e.second;
			for (int i = 0; i <= K; ++i) dp[1 - t][i] = dp[t][i] + (i >= w ? dp[t][i - w] : 0);
			t = 1 - t;
		}
		*/

		i64 tmp = 1;
		//for (int i = 0; i <= K; ++i) tmp += dp[t][i];
		for (auto e : grps) {
			int w = e.second;
			for (int i = 1; i <= K; ++i) tmp += C[w][i];
		}

		int pop = __builtin_popcount(m) % 2;
		if (pop == 1) tmp = -tmp;
		// printf("%d: %lld\n", m, tmp);
		ret += tmp;
	}
	printf("%lld\n", ret);
	return 0;
}