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 <iostream>
#include <cstring>
#define MN 55

typedef long long ll;

char cnt[400000000];
ll C[MN][MN], ans = 0;
bool ok[MN]; int N = 0;
int n, m, S, T;
int a[MN], tot = 0; 

int main()
{
	scanf("%d%d%d%d", &n, &m, &S, &T);
	if((S & T) != S) return 0 * puts("0");
	for(int i = 0; i <= n; i++) C[i][0] = C[i][i] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j < i; j++)
			C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
	for(int i = 1; i <= n; i++)
		for(int j = 2; j <= m; j++)
			C[i][j] += C[i][j - 1];
			
	for(int i = 0; i < 18; i++) if(((S >> i) & 1) != ((T >> i) & 1)) N++, ok[i] = 1;
	for(int i = 1; i <= n; i++)
	{
		int x; scanf("%d", &x);
		if((x & S) != S || (x | T) != T) continue;
		++tot;
		for(int j = 17; j >= 0; j--)
			if(ok[j]) a[tot] = a[tot] * 2 + ((x >> j) & 1);
		for(int S = 0; S < (1 << N); S++)
		{
			int T = 0, w = 0;
			for(int j = N - 1; j >= 0; j--)
			{
				T *= 3;
				if((S >> j) & 1) w++, T += (a[tot] >> j) & 1;
				else T += 2;
			}
			ll v = 0;
			v -= C[cnt[T]][m];
			cnt[T]++;
			v += C[cnt[T]][m];
			if(w & 1) ans -= v;
			else ans += v;
		}
	}
	printf("%lld\n", ans);
}