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;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0); 
	int N, K, S, T; cin >> N >> K >> S >> T; 
	long long com[55][55] = {}; 
	long long Com[55][55] = {}; 
	com[0][0] = 1; 
	for(int i = 0; i < 52; i++){
		for(int j = 0; j <= i; j++){
			com[i+1][j] += com[i][j]; 
			com[i+1][j+1] += com[i][j]; 
		}
	}
	for(int i = 0; i < 52; i++){
		Com[i][0] = 1; 
		for(int j = 1; j <= i; j++){
			Com[i][j] = Com[i][j-1] + com[i][j]; 
		}
	}
	vector<int> A, B; 
	for(int i = 0; i < N; i++){
		int a; cin >> a; 
		if((a & S) != S || (a | T) != T) continue; 
		A.push_back(a); 
	}
	vector<int> d; 
	for(int i = 0; i < 18; i++){
		if(((S >> i) & 1) && !((T >> i) & 1)){
			cout << 0 << "\n"; return 0; 
		}
	}
	for(int i = 0; i < 18; i++){
		if(((S >> i) & 1) || !((T >> i) & 1)) continue;
		d.push_back(i); 
	}
	for(auto a : A){
		int b = 0; 
		for(int i = 0; i < d.size(); i++){
			b += (((a >> d.at(i)) & 1) << i); 
		}
		B.push_back(b); 
	}
	int D = d.size(); 
	long long ans = 0; 
	for(int bit = 0; bit < (1 << D); bit ++){
		vector<int> C; 
		long long num = 0; 
		for(auto b : B){
			C.push_back(b & bit); 
		}
		sort(C.begin(), C.end()); 
		C.push_back(1145141919); 
		if(!C.size()) continue; 
		int now = C.at(0); int cons = 1; 
		for(int c = 1; c < (int) C.size(); c++){
			if(C.at(c) == now) cons ++; 
			else{
				if(cons > K) num += Com[cons][K] - 1; 
				else num += (1LL << cons) - 1; 
				now = C.at(c); cons = 1; 
			}
		}
		int m = __builtin_popcount(bit);
		if(m % 2) ans -= num; 
		else ans += num; 
	}
	cout << ans << "\n"; 
}