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 long double ld;
#define mp make_pair
#define PI pair<ll,ll>
#define poly vector<ll>
#define mem(a) memset((a),0,sizeof(a))
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x.size()))
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
ll rnd(){
	ull ans=0;
	For(i,0,4)ans=ans<<15^rand();
	return ans%((ull)1<<63);
}
const int N=55;
int n,k;
ll s,t,f[18][2],ycl[N],c[N][N],a[N],ans;
void dfs(int p,ll zt,int xs){
	if(!zt)return;
	if(p==18){
		ans+=ycl[__builtin_popcountll(zt)]*xs; 
		//cout<<ans<<" "<<xs<<" "<<zt<<endl;
		return;
	}
	//if(p<3)cout<<zt<<" "<<f[p][0]<<" "<<f[p][1]<<endl;
	if(s>>p&1){
		dfs(p+1,zt&f[p][1],xs);
	}else if(!(t>>p&1)){
		dfs(p+1,zt&f[p][0],xs);
	}else{
		dfs(p+1,zt&f[p][0],-xs);
		dfs(p+1,zt&f[p][1],-xs);
		dfs(p+1,zt,xs);
	}
}
int main(){
	#ifdef Brollan
		freopen("1.in","r",stdin);
	#endif
	n=read(),k=read(),s=read(),t=read();
	For(i,0,n)For(j,c[i][0]=1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j]);
	For(i,0,n)For(j,1,k)ycl[i]+=c[i][j];
	For(i,0,n-1)a[i]=read();
	For(i,0,17){
		For(j,0,n-1)if(a[j]>>i&1)f[i][1]|=(ll)1<<j;
		f[i][0]=f[i][1]^(((ll)1<<n)-1);
	}
	For(i,0,17)if((s>>i&1)&&(t>>i&1)==0){
		puts("0"); exit(0);
	}
	//puts("fj");
	dfs(0,((ll)1<<n)-1,1);
	cout<<ans<<endl;
}