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;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;



int n, k, S, T;
// S: AND
// T: OR

bool compat(int x) {
    if ((x|T) != T) return false;
    if ((x&S) != S) return false;

    return true;
}


bool ok(ll mask) {
    // check S
    for (int i=0; i<18; i++) {
	if (!(S>>i&1)) {
	    if (mask>>i&1) {
		if (!((mask>>(i+18))&1)) {
		    return false;
		}
	    }
	}
    }

    // check T
    for (int i=0; i<18; i++) {
	if (T>>i&1) {
	    if (!(mask>>i&1)) {
		return false;
	    }
	} else {
	    if (mask>>i&1) {
		return false;
	    }
	}
    }



    return true;
}


ll make(ll x, ll mask) {
    mask |= x;
    x = (~x)&((1<<18)-1);
    mask |= (x<<18);

    return mask;
}

unordered_map<ll, ll> dp[55]; // dp[size][have]

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>k>>S>>T;
    if ((S&T) != S) out(0);

    vector<int> a;
    while (n--) {
	int x;
	cin>>x;
	if (compat(x)) {
	    a.push_back(x);
	}
    }

    dp[0][0] = 1;


    for (int x: a) {
	for (int sz=k-1; sz>=0; sz--) {
	    for (auto p: dp[sz]) {
		ll nmask = make(x, p.first);
		dp[sz+1][nmask] += p.second;
	    }
	}
    }

    ll res = 0;
    for (int i=1; i<=k; i++) {
	for (auto p: dp[i]) {
	    if (ok(p.first)) {
		res += p.second;
	    }
	}
    }

    cout<<res<<endl;
    
    return 0;
}