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 meow(args...) fprintf(stderr, args)
const int N = 50;
int a[N], cnt[1 << 18];
int main()
{
	int n, k, s, t;
	long long ans = 0, csum[N + 1] = {};
	scanf("%d%d%d%d", &n, &k, &s, &t);
	for (int i = 0; i < n; ++i) {
		scanf("%d", a + i);
		if ((a[i] & s) != s || (a[i] | t) != t) {
			--i;
			--n;
		}
	}
	if (n == 0)
		goto nosolution;
	for (int i = 1; i <= n; ++i) {
		long long com = 1;
		for (int j = 1; j <= i && j <= k; ++j)
			csum[i] += com = com * (i - j + 1) / j;
	}
	for (int i = n; i >= 1; --i)
		csum[i] -= csum[i - 1];
	for (int mask = 1 << 18; mask; ) {
		long long cur = 0;
		mask = (mask - 1) & (s ^ t);
		for (int i = 0; i < n; ++i)
			cur += csum[++cnt[a[i] & mask]];
		if (__builtin_popcount(mask) & 1)
			ans -= cur;
		else
			ans += cur;
		for (int i = 0; i < n; ++i)
			cnt[a[i] & mask] = 0;
	}
nosolution:
	printf("%lld\n", ans);
	return 0;
}