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<cstring>
#define N 52
#define M 262150
using namespace std;
int a[N],p1[N],p2[N];
long long C[N][N],choose[N];
long long ans;
bool need[N],bo[N];
int n,m,s1,s2;
int get(int x,int y)
{
	int ps=x/(1<<(y-1));
	return ps%2;
}
void dfs(int k,int xi)
{
	if (k>18)
	{
		if (!bo[1])
		{
			k++;k--;
		}
		for (int i=1;i<=n;i++)
		{
			if (!need[i]) continue;
			int ands=0,ors=0;
			for (int j=1;j<=18;j++)
			{
				ors=(ors+(1<<(j-1)));
				if (bo[j]) continue;
				int sp=get(a[i],j);
				ands=(ands+(1<<(j-1)));
				if (sp==1) ors=(ors-(1<<(j-1)));
				if (sp==1) ands=(ands-(1<<(j-1)));
			}
			int num=1;
			for (int j=i+1;j<=n;j++)
			{
				if (!need[j]) continue;
				int ps1=a[j]&ands;
				int ps2=a[j]|ors;
				if (ps1!=0||ps2!=((1ll<<18)-1)) continue;
				num++;
			}
			ans=(ans+xi*(choose[num-1]));
		}
		return ;
	}
	if (p1[k]==0&&p2[k]==1)
	{	
		bo[k]=true;
		dfs(k+1,xi);
		bo[k]=false;
		dfs(k+1,-xi);
		return;
	}
	if (p1[k]==1)
		for (int i=1;i<=n;i++)
			if (get(a[i],k)!=1)
				need[i]=false;
	if (p2[k]==0)
		for (int i=1;i<=n;i++)
			if (get(a[i],k)!=0)
				need[i]=false;
	dfs(k+1,xi);
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&s1,&s2);
	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]+C[i-1][j-1]);
	choose[0]=1;
	for (int i=1;i<=n;i++)
		for (int j=0;j<m;j++)
			choose[i]=choose[i]+C[i][j];
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=18;i++)
	{
		p1[i]=get(s1,i);
		p2[i]=get(s2,i);
		if (p1[i]==1&&p2[i]==0)
		{
			printf("0\n");
			return 0;
		}
	}
	memset(bo,true,sizeof(bo));
	memset(need,true,sizeof(need));
	dfs(1,1);
	printf("%lld\n",ans);
}