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:
//Author: ReseeCher
#include<bits/stdc++.h>
#define LL long long
#define F(x,y,z) for(int x=y;x<=z;++x)
#define D(x,y,z) for(int x=y;x>=z;--x)
#define ckmax(a,b) (a)=max(a,b)
#define ckmin(a,b) (a)=min(a,b)
#define pb push_back
using namespace std;
const int N=262144;
const int M=55;
LL R(){
    LL ans=0,f=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if (c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) ans=ans*10+c-'0';
    return ans*f;
}
int nn,n,K,S,T;
LL a[N];
int q[N];
int cnt[N];
LL C[55][55];
void FWT(){
	for(int mid=1;mid<N;mid<<=1)
		for(int l=0;l<N;l+=mid+mid)
			for(int k=l;k<l+mid;++k)
				a[k+mid]+=a[k];
}
LL Sol(int st){
	memset(a,0,sizeof(a));
	F(i,st+1,n)
		a[q[i]^q[st]]++;
	FWT();
	LL an=0;
	int uT=T-(T&S);
	for(int i=uT;i;i=uT&(i-1)){
		int fg=((cnt[uT]-cnt[i])&1)?-1:1;
		an+=fg*C[a[i]][K-1];
	}
	int i=0;
	int fg=((cnt[uT]-cnt[i])&1)?-1:1;
	an+=fg*C[a[i]][K-1];
	return an;
}
int main(){
	//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
	F(i,1,N-1)cnt[i]=cnt[i>>1]+(i&1);
	F(i,0,M-1)C[i][0]=1;
	F(i,1,M-1)F(j,1,i)C[i][j]=C[i-1][j-1]+C[i-1][j];
	F(i,0,M-1)F(j,1,M-1)C[i][j]+=C[i][j-1];
	
	nn=R();K=R();S=R();T=R();
	F(i,1,nn){
		int x=R();
		if((x&S)!=S)continue;
		if((x&T)!=x)continue;
		q[++n]=x;
	}
	LL ans=0;
	F(i,1,n)ans+=Sol(i);
	cout<<ans<<'\n';
    return 0;
}