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 forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << a << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair
 
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 55;
const int L = 18;

int n,k,s,t;
ll a[N], comb[N][N], cnt[1<<L];

ll solve() {
    cin >> n >> k >> s >> t;
    if ((s & t) != s) return 0;
    {
        int sz = 0;
        forn(_,n) {
            ll x; cin >> x;
            if ((s & x) != s) continue;
            if ((x | t) != t) continue;
            a[sz++] = x-s;
        }
        n = sz;
    }
    ll ans = 0;
    forn(i,n) {
        memset(cnt, 0, sizeof cnt);
        forsn(j,i+1,n) cnt[a[j]^a[i]]++;
        forn(bit,L) forn(mask,1<<L) if ((mask>>bit)&1)
            cnt[mask] += cnt[mask - (1<<bit)];
        forn(mask,1<<L) cnt[mask] = comb[cnt[mask]][k-1];
        forn(bit,L) forn(mask,1<<L) if ((mask>>bit)&1)
            cnt[mask] -= cnt[mask - (1<<bit)];
        ans += cnt[t-s];
    }
    return ans;
}

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

    forn(n,N) {
        comb[n][0] = 1;
        forsn(r,1,n+1) comb[n][r] = comb[n-1][r-1] + comb[n-1][r];
    }
    forn(n,N) {
        forsn(r,1,N) comb[n][r] += comb[n][r-1];
    }

    cout << solve() << endl;

    return 0;
}