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;



int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N, K, S, T; cin >> N >> K >> S >> T;
    vector<int> bit;
    bool ok = true;
    for (int i = 0; i < 18; i++) {
        bool s = S & (1 << i);
        bool t = T & (1 << i);
        if (s && !t) ok = false;
        if (!s && t) bit.emplace_back(i);
    }

    if (!ok) {
        cout << 0 << "\n";
        return 0;
    }

    const int B = bit.size();
    vector<int> X;
    for (int i = 0; i < N; i++) {
        int A, C = 0; cin >> A;
        if ((A & S) == S && (A | T) == T) {
            for (int i = 0; i < B; i++) {
                if (A & (1 << bit[i])) C |= 1 << i; 
            }
            X.emplace_back(C);
        }
    }
    
    long long Bicom[51][51];
    memset(Bicom, 0, sizeof(Bicom));
    Bicom[0][0] = 1;
    for (int n = 0; n < 50; n++) {
        for (int r = 0; r <= n; r++) {
            Bicom[n+1][r] += Bicom[n][r];
            Bicom[n+1][r+1] += Bicom[n][r];
        }
    }

    const int M = X.size();
    const int mask = (1 << B) - 1;
    long long Ans = 0;
    for (int k = 1; k <= K; k++) Ans += Bicom[M][k];
    
    for (int first = 0; first < M; first++) {
        vector<long long> C(1 << B, 0);
        for (int i = first+1; i < M; i++) {
            int same = (X[first] ^ X[i]) ^ mask;
            C[same]++;
        }
        
        for (int i = B-1; i >= 0; i--) {
            for (int j = 0; j < (1 << B); j++) {
                if ((1<<i) & j) C[j^(1<<i)] += C[j];
            }
        }

        for (int i = 0; i < (1 << B); i++) {
            int x = C[i]; C[i] = 0;
            for (int k = 1; k < K; k++) {
                C[i] += Bicom[x][k];
            }
        }

        for (int i = B-1; i >= 0; i--) {
            for (int j = 0; j < (1 << B); j++) {
                if ((1<<i) & j) C[j^(1<<i)] -= C[j];
            }
        }
        
        for (int i = 1; i < (1 << B); i++) Ans -= C[i];
        Ans--;
    }

    cout << Ans << "\n";

    return 0;
}