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 int K = 18, N = 55;
long long C[N][N];

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

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

bool between(int sub, int super, int x) {
    return (sub&x) == sub && (super&x) == x;
}

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

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

    vector<int> v(n);
    for (int i=0; i<n; i++) cin>>v[i];

    long long ans = 0;
    for (int mask = 0; mask < (1<<K); mask++) {
        if (!between(S, T, mask))  continue;

        vector<int> vv;
        for (int i=0; i<n; i++)
            if (between(S, T, v[i]))
                vv.push_back(v[i] & (~mask));

        sort(vv.begin(), vv.end());

        long long ww = 0;
        while (vv.size()) {
            int last = vv.back();
            int cnt = 0;
            while (vv.size() && vv.back() == last)  cnt++, vv.pop_back();
            ww += C[cnt][k]-1;
        }

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