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;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000

long long get(long long num,long long K){
	long long ret = 0;
	long long temp = 1;
	for(int i=0;i<K;i++){
		temp *= num-i;
		temp /= i+1;
		ret += temp;
	}
	return ret;
}	

int main(){
	
	int N,K,S,T;
	cin>>N>>K>>S>>T;
	
	for(int i=0;i<18;i++){
		int a = (S>>i)&1;
		int b = (T>>i)&1;
		if(a==1&&b==0){
			cout<<0<<endl;
			return 0;
		}
	}
	
	vector<int> A;
	for(int i=0;i<N;i++){
		int x;
		cin>>x;
		bool f = true;
		for(int j=0;j<18;j++){
			int t = (x>>j)&1;
			int a = (S>>j)&1;
			int b = (T>>j)&1;
			if(t==1&&b==0){
				f=false;
				break;
			}
			if(t==0&&a==1){
				f=false;
				break;
			}
		}
		if(f){
			A.push_back(x);
		}
	}
	
	N = A.size();
	
	vector<int> valid;
	for(int i=0;i<18;i++){
		int a = (S>>i)&1;
		int b = (T>>i)&1;
		if(a==0&&b==1){
			valid.push_back(i);
		}
	}
	
	vector<long long> calc(N+1);
	for(int i=0;i<=N;i++)calc[i] = get(i,K);
	
	long long ans = 0;
	for(int i=0;i<(1<<valid.size());i++){
		int cnt = 0;
		map<int,long long> mp;
		
		int X = 0;
		for(int j=0;j<valid.size();j++){
			if((i>>j)&1){
				X ^= (1<<valid[j]);
				cnt++;
			}
		}
		
		for(int j=0;j<N;j++){
			mp[A[j]&X] ++;
		}
		long long temp = 0;
		for(auto a:mp){
			temp += calc[a.second];
		}
		if(cnt%2==0)ans += temp;
		else ans -= temp;
	}
	
	cout<<ans<<endl;
			

		
		
	return 0;
}