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 int long long
long long c[55][55];
int a[55],fl[55],cnt[1<<18];
set<int>::iterator it;
signed main(){
	c[0][0]=1;
	for(int i=1;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];
	}
	int n,k,S,T;
	cin>>n>>k>>S>>T;
	for(int i=0;i<=50;++i)
		for(int j=1;j<=k;++j)
			c[i][j]+=c[i][j-1];
	for(int i=1;i<=n;++i)
		cin>>a[i],fl[i]=1;
	for(int i=0;i<18;++i){
		int bit1=(S>>i)&1,bit2=(T>>i)&1;
		if(bit1==1 && bit2==0) return cout<<0,0;
	}
	vector<int> vec;
	set<int> se;
	for(int i=1;i<=n;++i)
		if(((S&a[i])==S) && ((a[i]&T)==a[i]))vec.push_back(a[i]);
	//cout<<vec.size()<<endl;
	int ans=0,sum=0;
	for(int mask=0;mask<(1<<18);++mask){//容斥,至多i位不合法 
		int fl=0;se.clear();
		for(int i=0;i<18;++i)
			if(((mask>>i)&1) && ((S>>i)&1)==((T>>i)&1)){
				fl=1;break;
			}
		if(fl) continue;
		for(int i=0;i<vec.size();++i)
			cnt[vec[i]&mask]++,se.insert(vec[i]&mask);
		sum=0;
		for(it=se.begin();it!=se.end();++it)
			sum+=c[cnt[*it]][k]-1;
		for(int i=0;i<vec.size();++i)
			cnt[vec[i]&mask]=0;
		for(int i=0;i<18;++i)
			if((mask>>i)&1) sum=-sum;
		ans+=sum; 
	}
	cout<<ans;
	return 0;
}