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 int long long
using namespace std;
const int N=55;

int read()
{
	int s=0;
	char c=getchar(),lc='+';
	while (c<'0'||'9'<c) lc=c,c=getchar();
	while ('0'<=c&&c<='9') s=s*10+c-'0',c=getchar();
	return lc=='-'?-s:s;
}
void write(int x)
{
	if (x<0)
	{
		putchar('-');
		x=-x;
	}
	if (x<10) putchar(x+'0');
	else
	{
		write(x/10);
		putchar(x%10+'0');
	}
}
void print(int x,char c='\n')
{
	write(x);
	putchar(c);
}
map<int,int>Map;
int m,a[N],C[N][N];
bool check(int x,int y)
{
	return x==(x&y);
}

signed main()
{
	int n=read(),k=read(),s=read(),t=read(),ans=0;
	for (int i=1;i<=n;i++)
	{
		int x=read();
		if (check(s,x)&&check(x,t)) a[++m]=x;
	}
	n=m;
	memset(C,0,sizeof(C));
	for (int i=0;i<=n;i++) C[i][0]=1;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j];
	for (int i=1;i<=n;i++)
	for (int j=1;j<=k;j++) C[i][j]+=C[i][j-1];
	for (int p=0;p<(1<<18);p++)
	{
		bool flag=1;
		for (int i=0;i<18;i++)
		if ((p>>i&1)&&(s>>i&1)==(t>>i&1))
		{
			flag=0;
			break;
		}
		if (!flag) continue;
		Map.clear();
		int sum=0;
		for (int i=1;i<=n;i++) Map[a[i]&p]++;
		for (int i=1;i<=n;i++)
		if (Map[a[i]&p])
		{
			sum+=C[Map[a[i]&p]][k]-1;
			Map[a[i]&p]=0;
		}
		for (int i=0;i<18;i++) if (p>>i&1) sum=-sum;
		ans+=sum;
	}
	print(ans);

	return 0;
}