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 <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
ll comb[51][51];
ll c[51];
int main()
{
	int n, k, s, t; cin>>n>>k>>s>>t;
	int a[51];
	for(int i=0; i<n; i++) cin>>a[i];
	if((s&t)!=s){
		cout<<0<<endl;
		return 0;
	}
	for(int i=0; i<=n; i++){
		comb[i][0]=comb[i][i]=1;
		for(int j=1; j<i; j++){
			comb[i][j]=comb[i-1][j-1]+comb[i-1][j];
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=k; j++) c[i]+=comb[i][j];
	}
	vector<ll> vx;
	ll x0=(1ll<<n)-1;
	for(int i=0; i<18; i++){
		if(s&(1<<i)){
			ll y=0;
			for(int j=0; j<n; j++){
				if(a[j]&(1<<i)) y^=(1ll<<j);
			}
			x0&=y;
			continue;
		}else if(!(t&(1<<i))){
			ll y=0;
			for(int j=0; j<n; j++){
				if(!(a[j]&(1<<i))) y^=(1ll<<j);
			}
			x0&=y;
			continue;
		}
		ll x=0;
		for(int j=0; j<n; j++){
			if(a[j]&(1<<i)) x^=(1ll<<j);
		}
		vx.push_back(x);
	}
	if(x0==0){
		cout<<0<<endl;
		return 0;
	}
	int m=vx.size();
	ll ans=c[popcountll(x0)];
	for(int i=1; i<(1<<m); i++){
		for(int l=0; l<n; l++){
			if(!(x0&(1ll<<l))) continue;
			ll s=x0;
			for(int j=0; j<m; j++){
				if(!(i&(1<<j))) continue;
				if(vx[j]&(1ll<<l)){
					s&=vx[j];
				}else{
					s&=((1ll<<n)-1-vx[j]);
				}
			}
			bool dame=0;
			for(int p=0; p<l; p++){
				if(s&(1ll<<p)){
					dame=1; break;
				}
			}
			if(!dame){
				if(popcount(i)&1) ans-=c[popcountll(s)];
				else ans+=c[popcountll(s)];
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}