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 int long long 
using namespace std;
typedef pair<int,int> ii;

int fact[200];
int dp[270005];

int memo[52][52];
int preS[52][52];
int choose(int N, int C){
	if(C == -1) return 0;
	if(C > N) return 0;
	if(C == 0) return 1;
	if(memo[N][C] != 0) return memo[N][C];
	return memo[N][C] = choose(N-1,C) + choose(N-1,C-1);
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	fact[0] = 1;
	
	int n,K,A,O; cin >> n >> K >> A >> O;
	
	int arr[n];
	for(int i = 0;i < n;i++) cin >> arr[i];
	
	int X = A ^ O;
	
	if((X & A) != 0){
		cout << 0; return 0;
	}
	vector<int> v;
	for(int i = 0;i < n;i++){
		bool can = true;
		for(int b = 0;b < 18;b++){
			if(X & (1<<b)) continue;
			
			if((O & (1<<b)) == (arr[i] & (1<<b))) continue;
			else can = false;
		}
		
		if(can) v.push_back(arr[i]);
	}	
	
	for(int i = 0;i <= 50;i++){
		for(int k = 1;k <= 50;k++){
			preS[i][k] = choose(i,k);
			if(k != 0) preS[i][k] += preS[i][k-1];
		}
	}
	
	//count complement
	int OV = 0;
	int ans = 0;
	
	for(int mask = 1;mask < 1<<18;mask++){
		int val = 0;
		if((mask & X) != mask) continue;
		
		unordered_map<int,int> M;
		for(int x : v){
			M[mask & x]++;
		}
		
		for(ii x : M){
			val += preS[x.second][K];
		}
		
		int par = __builtin_popcountll(mask);
		
		//cout << mask << " " << k << " " << val << " " << "\n";
		if(par & 1) ans += val;
		else ans -= val;
	}
	
	
	//cout << k << " " << ans << "\n";
	
	OV += preS[v.size()][K] - ans;
	
	
	cout << OV;
	
}