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>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
const int mod=1000000007;
int add(int a, int b)
{
	int c=a+b;
	if(c>=mod)c-=mod;
	return c;
}
int dif(int a, int b)
{
	int c=a-b;
	if(c<0)c+=mod;
	return c;
}
int mlt(int a, int b)
{
	long long c=a*1LL*b;
	return c%mod;
}
int bp(int a, int b)
{
	if(b==0)return 1;
	if(b%2==0)
	{
		int val=bp(a, b/2);
		return mlt(val, val);
	}
	if(b%2==1)
	{
		int val=bp(a, b-1);
		return mlt(val, a);
	}
}
int inv(int a)
{
	return bp(a, mod-2);
}
int ibit(int mask, int i)
{
	return (mask>>i)%2;
}
void outp(vector<vector<int>>&v)
{
	for(int i=0; i<v.size(); i++)
	{
		for(int j=0; j<v[i].size(); j++)cout<<v[i][j]<<' ';
		cout<<endl;
	}
	cout<<endl;
}
int main()
{
	int n;
	vector<vector<long long>> c(60, vector<long long>(60));
	c[0][0]=1;
	for(int i=1; i<60; i++)
	{
		c[0][i]=1;
		c[i][i]=1;
		for(int j=1; j<i; j++)c[j][i]=c[j][i-1]+c[j-1][i-1];
	}
	int k, s, t;
  long long ans=0;
	cin>>n>>k>>t>>s;
	vector<long long> val(60);
	for(int i=1; i<60; i++)
	{
		long long bans=0;
		for(int j=1; j<=k; j++)
		{
			bans+=c[j][i];
		}
		val[i]=bans;
	}
	vector<int>v;
	vector<int>gb;
	for(int i=0; i<18; i++)
	{
		if(ibit(s, i)==0)
			if(ibit(t,i)==1)ans=-1;
		if(ibit(s, i)==1)
			if(ibit(t,i)==0)gb.push_back(i);
	}
	for(int i=0; i<n; i++)
	{
		int x;
		cin>>x;
		int vl=0;
		for(int j=0; j<18; j++)
		{
			if(ibit(s, j)==0)
				if(ibit(x,j)==1)vl++;
			if(ibit(t, j)==1)
				if(ibit(x,j)==0)vl++;
		}
		if(vl==0)
		{
			v.push_back(x);
	//		cout<<x<<' ';
		}
	}
	vector<int>used(1<<18);
	if(ans==-1)cout<<0<<endl;
	else{
		for(int mask=0; mask<(1<<gb.size()); mask++)
		{
			int sn=0;
			for(int i=0; i<gb.size(); i++)
				if(ibit(mask, i))
					sn++;
			sn=sn%2;
			int vl=0;
			for(int i=0; i<gb.size(); i++)
				if(ibit(mask, i))
					vl+=(1<<gb[i]);
			vector<int>cur;
			for(int i=0; i<v.size(); i++)
			{
				int cr=v[i]&vl;
				used[cr]++;
				cur.push_back(cr);
			}
			for(int i=0; i<cur.size(); i++)
			{
				int vd=cur[i];
				long long ad=val[used[vd]];
				used[vd]=0;
				if(sn==0)ans+=ad;
				else ans-=ad;
			}
		}
		cout<<ans<<endl;
	}
}