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];
int cnt[1<<K];

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];
}

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 ((S&mask) != S || (T&mask) != mask)  continue;

        vector<int> vv;
        for (int i=0; i<n; i++) {
            if ((S&v[i]) != S || (T&v[i]) != v[i])  continue;
            int z = v[i] & (~mask);
            cnt[z]++;
            vv.push_back(z);
        }

        long long ww = 0;
        for (int x: vv){
            ww += C[cnt[x]][k]-1;
            cnt[x] = 0;
        }

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