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>
using namespace std;
#define ll long long

ll c[60][60],f[60];
int num[110],h[110];
int cnt[262144],d[110],n,k,s,t,tt;

int Cnt[262144];
bool vis[262144];

inline int rd()
{
	int x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

inline void pre_gao()
{
	for (int i=0;i<=50;i++)
	{
		c[i][0]=1;
		for (int j=1;j<=i;j++) c[i][j]=c[i-1][j-1]+c[i-1][j];
	}
	for (int i=0;i<=50;i++) for (int j=1;j<=k;j++) f[i]+=c[i][j];
}

inline ll work(int x)
{
	for (int i=1;i<=n;i++) Cnt[h[i]&x]++;
	ll res=0;
	for (int i=1;i<=n;i++) if (!vis[h[i]&x]) vis[h[i]&x]=true,res+=f[Cnt[h[i]&x]];
	for (int i=1;i<=n;i++) vis[h[i]&x]=Cnt[h[i]&x]=0;
	return res;
}

int main()
{
	n=rd();k=rd();s=rd();t=rd();pre_gao();
	for (int i=1;i<=n;i++)
	{
		num[i]=rd();
		if ((num[i]&s)!=s||(num[i]|t)!=t) n--,i--;
	}
	if (!n) { puts("0");return 0; }
	for (int i=0;i<18;i++) if (((s^t)>>i)&1)
	{
		if ((s>>i)&1) { puts("0");return 0; }
		d[++tt]=i;
	}
	for (int i=1;i<=n;i++) for (int j=1;j<=tt;j++) if ((num[i]>>d[j])&1) h[i]|=(1<<(j-1));
	for (int i=1;i<(1<<tt);i++) cnt[i]=cnt[i>>1]+(i&1);
	ll ans=0;
	for (int i=0;i<(1<<tt);i++)
	{
		if (cnt[i]&1) ans-=work(i);
		else ans+=work(i);
	}
	printf("%lld\n",ans);
	return 0;
}