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 pop_count(int bits){
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main(){
    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 a;
        cin >> a;
        if((a&S) == S && (a|T) == T) A.push_back(a-S);
    }
    T -= S;
    N = A.size();
    K = min(K, N);

    uint64_t comb[51][51] = {0};
    comb[0][0] = 1;
    for(int i=1; i<=N; i++){
        comb[i][0] = 1;
        for(int j=1; j<=i; j++) comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
    }

    uint64_t sub[51] = {0};
    for(int i=0; i<=N; i++) for(int j=0; j<K; j++) sub[i] += comb[i][j];

    uint64_t ans = 0;
    for(int i=0; i<N; i++){
        for(int b=T; ; b=(b-1)&T){
            int cnt = 0;
            int n1 = b&A[i];
            int n0 = b-n1;
            for(int j=i+1; j<N; j++) if((A[j]&n1) == n1 && (A[j]&n0) == 0) cnt++;
            uint64_t res = sub[cnt];
            if(pop_count(b)%2) res *= -1;
            ans += res;
            if(b == 0) break;
        }
    }

    cout << ans << endl;
    return 0;
}