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>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> void read(T &x){
	int f=0; x=0; char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f|=(ch=='-');
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	if(f) x=-x;
}

const int N=55;
int a[N],w[N],n,m,K,S,T,aim;
ull C[N][N],ans;

int main(){
	read(n),read(K);
	read(S),read(T);
	rep(i,1,n){
		read(a[++m]);
		if((a[m]&S)!=S) m--;
		else if((a[m]|T)!=T) m--;
	}
	n=m,aim=(~S)&T;
	C[0][0]=1;
	rep(i,1,n){
		C[i][0]=1;
		rep(j,1,n){
			C[i][j]=C[i-1][j]+C[i-1][j-1];
		}
	}
	rep(l,1,n){
		rep(r,l+1,n){
			w[r]=(a[l]^a[r])&aim;
		}
		for(int s=aim;;s=(s-1)&aim){
			int tot=0;
			rep(r,l+1,n){
				tot+=((w[r]|s)==s);
			}
			ull sum=0;
			rep(i,0,K-1){
				sum+=C[tot][i];
			}
			if(__builtin_popcount(aim^s)%2==0){
				ans+=sum;
			}
			else{
				ans-=sum;
			}
			if(!s) break;
		}
	}
	cout<<ans<<endl;
	return 0;
}