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;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
template<class T> inline void dmin(T& x,T y){ y<x?x=y:0; }
template<class T> inline void dmax(T& x,T y){ y>x?x=y:0; }
template<class T> inline void dmin(T& x,vector<T> y){ 
	for(auto t:y) t<x?x=t:0;
}
template<class T> inline void dmax(T& x,vector<T> y){
	for(auto t:y) t>x?x=t:0;
}
ll f[20][2],c[55][55],ans=0;
int cnt[1<<25|5],a[55],n,k,S,T;
struct Initer{
	Initer(){
		cnt[0]=0;
		for(int i=1;i<1<<25;++i)
			cnt[i]=cnt[i-(i&-i)]+1;
		for(int i=0;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];
		}
		for(int i=0;i<=50;++i){
			for(int j=1;j<=50;++j)
				c[i][j]+=c[i][j-1];
			for(int j=0;j<=50;++j)
				c[i][j]--;
		}
	}
}__initer;
int bitcount(ll x){
	return cnt[x>>25]+cnt[x&((1<<25)-1)];
}
void dfs(int x,ll sta,int p){
//	printf("[%d %lld %d]\n",x,sta,p);
	if(x==18){
//		printf("[%lld %d %d]\n",sta,bitcount(sta),p);
//		exit(0);
		ans+=p*c[bitcount(sta)][k];
		return;
	}
	if(((S>>x)&1)==((T>>x)&1)){
		int flag=(S>>x)&1;
		dfs(x+1,sta&f[x][flag],p);
	}else{
		dfs(x+1,sta,p);
		dfs(x+1,sta&f[x][0],-p);
		dfs(x+1,sta&f[x][1],-p);
	}
}
int main(){
	scanf("%d%d%d%d",&n,&k,&S,&T);
	for(int i=0;i<n;++i){
		scanf("%d",&a[i]);
		for(int j=0;j<18;++j)
			f[j][(a[i]>>j)&1]|=1ll<<i;
	}
	dfs(0,(1ll<<n)-1,1);
	printf("%lld\n",ans);
	return 0;
}