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 MAX (ll)(1e5 + 7)
#define INF (ll)(1e18)
#define MOD (ll)(998244353)

using namespace std;
using ll = long long;
using cd = complex<double>;

const ll bc = 18, nn = 51;

ll nck[nn][nn];

ll solve (ll n, ll k) {
	if (k > n || n < 0 || k < 0) {
		nck[n][k] = 0;
		return 0;
	}
	if (nck[n][k] != -1) {
		return nck[n][k];
	}
	nck[n][k] = solve (n - 1, k) + solve (n - 1, k - 1);
	return nck[n][k];
}

int main () {
	ll n, k, s, t, lim = 0;
	cin >> n >> k >> s >> t;
	vector<ll> ve, ev, v;
	ll x = (1 << bc) - 1;
	for (ll i = 0; i < n; i++) {
		ll vv;
		cin >> vv;
		if ((vv & s) >= s && (vv | t) <= t) {
			v.push_back (vv);
		}
	}
	if (s & t < s) {
		cout << "0\n";
		return 0;
	}
	for (ll xx : v) {
		ll val = 0, i = 0;
		for (ll j = 0; j < bc; j++) {
			if (((s >> j) & 1) != ((t >> j) & 1)) {
				val |= ((xx >> j) & 1) << i;
				i++;
			}
		}
		lim = i;
		ve.push_back (val);
	}
	n = ve.size ();
	for (ll i = 0; i <= n; i++) {
		for (ll j = 0; j <= k; j++) {
			nck[i][j] = -1;
		}
	}
	nck[0][0] = 1;
	for (ll i = 0; i <= n; i++) {
		for (ll j = 0; j <= k; j++) {
			solve (i, j);
		}
	}
	for (ll i = 0; i <= n; i++) {
		for (ll j = 2; j <= k; j++) {
			nck[i][j] += nck[i][j - 1];
		}
	}
	ll all = nck[n][k], cc[1 << bc] = {};
	for (ll i = 1; i < (1 << lim); i++) {
		ll an = 0;
		for (ll x : ve) {
			cc[i & x]++;
		}
		for (ll x : ve) {
			if (cc[i & x]) {
				an += nck [cc[i & x]][k];
			}
			cc[i & x] = 0;
		}
		all += ((__builtin_popcount (i) & 1) ? -an : an);
	}
	cout << all << "\n";
}