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;

const long long K = 18, N = 55;

vector<long long> vv[1<<K];

long long C[N][N];

void pre() {
    for (long long i=0; i<N; i++) C[i][0] = 1;
    for (long long i=1; i<N; i++)
        for (long long j=1; j<N; j++)
            C[i][j] = C[i-1][j-1] + C[i-1][j];

    for (long long i=0; i<N; i++)
        for (long long j=1; j<N; j++)
            C[i][j] += C[i][j-1];
}

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


    long long n, k, S, T;
    cin>>n>>k>>S>>T;

    if ( (S&T) != S) {
        cout<<0<<endl;
        return 0;
    }

    for (long long i=0; i<n; i++) {
        long long x;
        cin>>x;

        if ((x&S) != S) continue;
        if ((x&T) != x) continue;

        for (long long mask = 0; mask < (1<<K); mask++) {
            if ((mask&S) != S) continue;
            if ((mask&T) != mask) continue;
            long long ans = 0;
            for (long long i=0; i<K; i++) {
                bool si = S & (1<<i);
                bool ti = T & (1<<i);
                if (si == ti)   continue;
                if ((mask & (1<<i)) == 0)       ans |= x&(1<<i);
            }
            vv[mask].push_back(ans);
        }
    }

    long long ans = 0;
    for (long long mask = 0; mask < (1<<K); mask++) {
        if ((mask&S) != S) continue;
        if ((mask&T) != mask) continue;
        sort(vv[mask].begin(), vv[mask].end());

        long long ww = 0;
        while (vv[mask].size()) {
            long long last = vv[mask].back();
            long long cnt = 0;
            while (vv[mask].size() && vv[mask].back() == last)  cnt++, vv[mask].pop_back();

            ww += C[cnt][k]-1;
        }

        long long bc = __builtin_popcount(mask);
        if (bc%2)   ans += ww;
        else        ans -= ww;
    }
    cout<<abs(ans)<<endl;
}