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;
typedef long long LL;
const int LOG = 18;
const int MAXN = 53;

LL nCr[MAXN][MAXN];

LL f(int n, int k) {
    LL ans = 0;
    for (int i = 1; i <= n && i <= k; i++) {
        ans += nCr[n][i];
    }
    return ans;
}

int main() {
    nCr[0][0] = 1;
    for (int n = 1; n < MAXN; n++) {
        nCr[n][0] = 1;
        for (int r = 1; r <= n; r++) {
            nCr[n][r] = nCr[n-1][r]+nCr[n-1][r-1];
        }
    }

    int n, k, s, t;
    cin >> n >> k >> s >> t;

    if ((s&t) != s) {
        cout << 0 << endl;
        return 0;
    }

    vector< int >A;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        bool okay = true;
        int y = 0;
        for (int j = 0, l = 0; j < LOG && okay; j++) {
            int _x = (x>>j)&1;
            int _s = (s>>j)&1;
            int _t = (t>>j)&1;

            if (_s == 1 && _x == 0)         okay = false;
            else if (_t == 0 && _x == 1)    okay = false;
            else if (_s == 0 && _t == 1) {
                y |= _x << l;
                l++;
            }
        }

        if (okay) {
//            cout << x << " -> " << y << endl;
            A.push_back(y);
        }
    }

    int L = 0;
    for (int j = 0; j < LOG; j++) {
        int _s = (s>>j)&1;
        int _t = (t>>j)&1;
        L += (_s==0)&&(_t==1);
    }

//    cout << "L : " << L << endl;

    LL ans = 0;
    for (int msk = 0; msk < (1<<L); msk++) {
        vector< int >B(A);
        for (int &x : B) x &= msk;
        sort(B.begin(), B.end());
//        cout << "mask: " << bitset<2>(msk) << endl;
//        for (int u : B) cout << u << " ";
//        cout << endl;

        LL z = 0;
        for (int i = 0; i < B.size(); i++) {
            int j = i;
            while (j+1 < B.size() && B[j+1]==B[i]) j++;
            z += f(j-i+1, k);
            i = j;
        }

        if (__builtin_popcount(msk)&1) ans -= z;
        else ans += z;
    }

    cout << ans << endl;


    return 0;
}