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<iostream>
using namespace std;
int N,K;
int S[18],T[18];
int A[50][18];
bool cA[50];
long cnt[55];
long comb[51][51];
void rd(int X[18])
{
	int Y;cin>>Y;
	for(int i=0;i<18;i++)X[i]=Y>>i&1;
}
int pc(long X)
{
	return __builtin_popcountll((long long)X);
}
int main()
{
	cin>>N>>K;
	rd(S);
	rd(T);
	for(int i=0;i<N;i++)
	{
		rd(A[i]);
		bool now=false;
		for(int j=0;j<18;j++)
		{
			if(S[j]==1&&A[i][j]==0||T[j]==0&&A[i][j]==1)
			{
				now=true;
				break;
			}
		}
		cA[i]=!now;
	}
	comb[0][0]=1;
	for(int i=1;i<=50;i++)
	{
		comb[i][0]=comb[i][i]=1;
		for(int j=1;j<i;j++)comb[i][j]=comb[i-1][j-1]+comb[i-1][j];
	}
	for(int i=0;i<=50;i++)
	{
		for(int j=1;j<=i&&j<=K-1;j++)cnt[i]+=comb[i][j];
	}
	for(int i=0;i<18;i++)
	{
		if(S[i]==1&&T[i]==0)
		{
			cout<<0<<endl;
			return 0;
		}
	}
	long ans=0;
	for(int i=0;i<N;i++)
	{
		if(!cA[i])continue;
		long ok=0;
		long check[18]={};
		for(int j=i+1;j<N;j++)
		{
			if(!cA[j])continue;
			ok|=1L<<j;
			for(int k=0;k<18;k++)
			{
				if(S[k]==0&&T[k]==1)
				{
					if(A[i][k]==A[j][k])check[k]|=1L<<j;
				}
			}
		}
		long now=cnt[pc(ok)];
		for(int j=1;j<1<<18;j++)
		{
			long take=ok;
			for(int k=0;k<18;k++)if(j>>k&1)take&=check[k];
			long X=cnt[pc(take)];
			if(pc(j)%2==0)now+=X;
			else now-=X;
		}
		ans+=now;
	}
	cout<<ans<<endl;
}