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:
/*
 * Since g++10 is released, some characters is not valid inside #if 0 :(
 * So, why not using clang++? :D

 * Date:
  echo -n '  ' && date +%Y.%m.%d # Just Run this (Type !!sh in Vim).

 * Solution:
  To be updated after "Accept".

 * Digression:

 * CopyRight:
          ▁▃▄▄▄▃▃▃▃▄▶
        ▗▇▀▔    ▔▔▔▔
       ▄▛   ▃▅━━■▄▂
      ▟▊   ▐▘     ▀▙
     ▟▜▌   ▐▖   ▋  ▐▍
    ▟▘ ▜   ▝▀▇▆●▘  ▐▌
  ▗▟▘   ▜▃       ▁▅▛
  ▔▀▼▅▄▃▃██▅▄▄▄▅■▀▔
        ▔▔▔▔▔▔
 */

#include <cstdio>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	inline operator ll () { ll x; return scanf("%lld", &x), x; }
	template<class T> inline void operator () (T &x) { x = *this; }
	template<class T, class ...A> inline void operator () (T &x, A &...a)
	{ x = *this; this -> operator () (a...); }
} read;

const int maxn = 55, maxk = 18;
int c[maxn];
ll C[maxn][maxn];

int main () {
	int n = read, m = read, a = read, b = read, ab = a ^ b;
	for (int k = 0; k < maxk; k ++)
		if (!(b >> k & 1) and a >> k & 1)
			return puts("0"), 0;

	int p = 0;
	for (int i = 1; i <= n; i ++) {
		int x = read;
		for (int k = 0; k < maxk; k ++)
			if (!(ab >> k & 1) and (x >> k & 1) != (a >> k & 1))
				goto fail;
		c[++ p] = x;
fail:;
	}
	n = p;
	if (m > n) m = n;

	for (int i = 0; i <= n; i ++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j ++)
			C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
	}

	ll ans = 0;
	for (int S = ab; S >= 0; S --) {
		S &= ab;
		ll now = 0;
		for (int i = 1; i <= n; i ++) {
			int x = 0;
			for (int j = i + 1; j <= n; j ++)
				if ((c[i] & S) == (c[j] & S))
					++ x;
			/* debug("%d\n", x); */
			for (int j = 0; j < m; j ++)
				now += C[x][j];
		}
		for (int k = 0; k < maxk; k ++)
			if (S >> k & 1)
				now = -now;
		/* debug("%d : %lld\n", S, now); */
		ans += now;
	}

	printf("%lld\n", ans);
}