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 pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long double ld;

const int inf = 1e9;
const ll inf64 = 1e18;

const int N = 55;
const int LOG = 18;
const int X = 1 << LOG;

int n, k;
int a[N], b[N], sz;
int S, T;
ll dp[N][X];
ll binom[N][N];
ll subs[X], cn[X];
ll overs[X];
int cnt_bit[X];

void precalc() {
    for (int i = 0; i < N; i++) {
        binom[i][0] = binom[i][i] = 1;
        for (int j = 1; j < i; j++) {
            binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
        }
    }
    for (int i = 0; i < N; i++)
        for (int j = 1; j < N; j++)
            binom[i][j] += binom[i][j - 1];

    for (int mask = 0; mask < X; mask++) {
        cnt_bit[mask] = __builtin_popcount(mask);
    }
}

bool le(int l, int r) {
    return (l & r) == l;
}

int main() {

    precalc();

#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k >> S >> T;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cn[a[i]]++;
    }

    for (int mask = 0; mask <= T; mask++) {
        for (int i = 0; i < n; i++) {
            if ((a[i] & mask) == a[i])
                subs[mask] |= (1ll << i);
            if ((mask & a[i]) == mask)
                overs[mask] |= (1ll << i);
        }
    }

    ll res = 0;

    for (int I = 0; I <= T; I++) {
        if (!le(S, I))
            continue;
        for (int J = I; J <= T; J = (J + 1) | I) {
            if (!le(I, J) || !le(J, T))
                continue;
            int tmp = cnt_bit[I ^ S] + cnt_bit[J ^ T];
            int cnt = __builtin_popcountl(subs[J] & overs[I]);
            int lc = I == 0 ? 0 : 1;
            int rc = min(cnt, k);
            ll tot = 0;
            if (lc <= rc)
                tot = binom[cnt][rc] - (lc ? binom[cnt][lc - 1] : 0);
            if (tmp % 2 == 0)
                res += tot;
            else
                res -= tot;
        }
    }


    cout << res << "\n";

    return 0;
}