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 vector<int> vi;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) int(a.size())
const int N=55;

int gi() {
	int x=0,o=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') o=-1,ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*o;
}

int n,k,s,t,m,a[N];
ll C[N][N];

void No() {
	cout<<0;exit(0);
}

int main() {
	cin>>n>>k>>s>>t;
	if((s&t)!=s) No();
	for(int i=0;i<N;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<N;i++) {
		C[i][0]=0;
		for(int j=1;j<=i;j++) C[i][j]+=C[i][j-1];
	}
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		if((a[i]&s)!=s||(a[i]&t)!=a[i]) --i,--n;
	}
	int key=0;
	for(int i=0;i<18;i++)
		if((s>>i&1)!=(t>>i&1)) key|=1<<i;
	m=__builtin_popcount(key);
	for(int i=1;i<=n;i++) {
		int now=0,val=0;
		for(int j=0;j<18;j++)
			if(key>>j&1) {
				if(a[i]>>j&1) val|=1<<now;
				++now;
			}
		a[i]=val;
		//cerr<<a[i]<<'\n';
	}
	ll ans=0;
	for(int i=0;i<(1<<m);i++) {
		int sgn=__builtin_parity(i)?-1:1;
		unordered_map<int,int> cnt;
		for(int j=1;j<=n;j++) ++cnt[a[j]&i];
		for(auto t:cnt) ans+=C[t.se][min(t.se,k)]*sgn;
	}
	cout<<ans;
	return 0;
}