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<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)

ll dp[55][400000];
ll C(ll n,ll k){
	if(n<k)return 0;
	if(k<0)return 0;
	return dp[k][n-k];
}
void init(){
	rep(i,55)rep(j,400000){
		if(i==0&&j==0){
			dp[i][j]=1;
		}
		else{
			dp[i][j]=0;
			if(i)dp[i][j]+=dp[i-1][j];
			if(j)dp[i][j]+=dp[i][j-1];
		}
	}
}

ll n,k,a[50],s,t;

ll calc(ll x){
	ll res=0;
	for(ll i=1;i<=k;i++){
		res+=C(x,i);
	}
	return res;
}

int main(){
	init();
	cin>>n>>k>>s>>t;
	rep(i,n)cin>>a[i];
	bool alv[50];
	rep(i,n)alv[i]=1;
	vector<ll> dig;
	rep(i,18){
		bool ss=s&(1<<i);
		bool tt=t&(1<<i);
		if(ss==1&&tt==0){
			cout<<0<<endl;
			return 0;
		}
		if(ss==1){
			rep(j,n)if(!(a[j]&(1<<i)))alv[j]=0;
		}
		else if(tt==0){
			rep(j,n)if(a[j]&(1<<i))alv[j]=0;
		}
		else{
			dig.push_back(i);
		}
	}
	int m=0;
	rep(i,n){
		if(alv[i]){
			a[m]=a[i];
			m++;
		}
	}
	n=m;
	ll ans=0;
	rep(i,(1<<(int)dig.size())){
		bool us[18];
		rep(j,18)us[j]=0;
		rep(j,dig.size()){
			if(i&(1<<j)){
				us[dig[j]]=1;
			}
		}
		unordered_map<ll,ll> mas;
		rep(j,n){
			ll res=0;
			rep(r,18){
				if(us[r]){
					res+=a[j]&(1<<r);
				}
			}
			mas[res]++;
		}
		ll res=0;
		for(auto t:mas){
			res+=calc(t.second);
		}
		
		int pcnt=0;
		rep(j,18)pcnt+=us[j];
		if(pcnt%2==0)ans+=res;
		else ans-=res;
	}
	cout<<ans<<endl;
}