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 FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=long long; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (56)
ll n, k, s, t, B[MAXN], ans, A[MAXN], co, C[MAXN][MAXN], ways[MAXN];
bool inc(ll x,ll bit) { return bool(x&(1<<bit)); }
int main(){
	FAST
	cin>>n>>k>>s>>t;
	FOR(j,0,17)if(inc(s,j) && !inc(t,j)) { cout<<"0\n"; return 0; }
	FOR(i,1,n)cin>>B[i];
	FOR(i,1,n){
		bool in=1;
		FOR(j,0,17){
			if(inc(s,j)==inc(t,j)){
				if(inc(B[i],j) ^ inc(s,j)) in=0;
			}
		}
		if(in)A[++co]=B[i];
	}
	n=co;
	FOR(i,0,MAXN-1)C[i][0]=1;
	FOR(i,1,MAXN-1)FOR(j,1,MAXN-1)C[i][j]+=C[i-1][j-1]+C[i-1][j];
	FOR(i,1,MAXN-1){
		FOR(j,1,min(i,k)){
			ways[i] += C[i][j];
		}
	}
	FOR(k,0,(1<<18)-1){
		bool bad=0;
		FOR(j,0,17)if(1<<j&k)if(inc(s,j)==inc(t,j))bad=1;
		if(bad)continue;
		vector<ll> v;
		FOR(i,1,n){
			v.eb(A[i] & k);
		}
		ll sign=((__builtin_popcount(k) & 1) ? -1 : 1);
		sort(all(v));
		for(ll s=0,e=0;s<v.size();s=e+1,++e){
			while(e+1<siz(v) && v[e] == v[e+1]) ++ e;
			ans += sign * ways[e-s+1];
		}
	}
	cout<<ans<<'\n';
}