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
// Amsal Shoma Ro Gaedan Ye Amal Pasandidas !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 55;
const ll Inf = 2242545357980376863LL;
const ll Log = 18;
const int K = (2<<18) + 10;

int n, s, k, t, a[N], A[N], mark[N];
vector<int> V, V2;
int C = 0;
ll ans = 0;
int cnt[K];
ll Z[N];

void Solve(){
	int al = (1 << C);
	for(auto &x : V2) cnt[x] ++;
	for(int i = 0; i < C; i++){
		for(int j = 0; j < al; j++){
			if(j >> i & 1) cnt[j] += cnt[j ^ (1 << i)];
		}
	}

	for(int j = 0; j < al; j++){
		ans += Z[cnt[j]] * (__builtin_popcount(j ^ (al - 1)) & 1 ? -1 : 1);
		cnt[j] = 0;
	}
}

ll ch[N][N];
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for(int i = 0; i < N; i++)
		for(int j = 0; j <= i; j++)
			ch[i][j] = (j == 0 ? 1 : ch[i - 1][j] + ch[i - 1][j - 1]);
	
	cin >> n >> k >> s >> t;
	
	for(int i = 0; i <= n; i++) for(int j = 1; j <= k; j++) Z[i] += ch[i][j - 1];

	for(int i = 1; i <= n; i++) cin >> a[i];
	int sb, tb;
	for(int i = 0; i < 18; i++){
		sb = s>>i & 1;
		tb = t>>i & 1;
		if(sb == tb){
			for(int j = 1; j <= n; j++){
				if((a[j] >> i & 1) != sb) mark[j] = 1;
			}
			continue;
		}
		if(sb == 1) return cout << "0\n", 0;
		for(int j = 1; j <= n; j++){
			A[j] = A[j] * 2 + (a[j] >> i & 1);
		}
		C ++;
	}
	for(int j = 1; j <= n; j++) if(!mark[j]) V.pb(A[j]);

	n = V.size();
	for(int i = 0; i < n; i++){
		V2.clear();
		for(int j = i + 1; j < n; j++) V2.pb(V[i] ^ V[j]);
		Solve();
	}
	cout << ans << '\n';
	return 0;
}
