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 N = 51, MAXN = 387420489, LOG = 18;
int pw[LOG] = {1}, dp[1<<LOG], a[N];
long long C[N][N], F[N], ans;
char cnt[MAXN];

int bit(int a, int i) {return (a>>i)&1;}
void BT(int i, int mask, int c) {
    if (i == -1) {
        if (c % 2 == 0) ans += F[(int)cnt[mask]];
        else ans -= F[(int)cnt[mask]];
        return ;
    }
    for (int j = 0; j < 3; j++) BT(i - 1, mask + j * pw[i], c + (j > 0));
    return ;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, k, A, O; cin >> n >> k >> A >> O;
    for (int i = 1; i < LOG; i++) pw[i] = pw[i - 1] * 3;
    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] + C[i - 1][j - 1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= min(i, k); j++) F[i] += C[i][j];
    // --------------------------------------------------------------------
    for (int i = 0; i < LOG; i++) if (bit(A, i) && (!bit(O, i))) return cout << 0 << "\n", 0;
    vector <int> vec, B;
    for (int i = 0; i < n; i++) {
        int x, val = 1; cin >> x;
        for (int j = 0; j < LOG; j++) {
            if (bit(x, j)) {
                if (!bit(O, j)) val = 0;
            } else {
                if (bit(A, j)) val = 0;
            }
        }
        if (val) vec.push_back(x);
    }
    n = vec.size();
    for (int i = 0; i < LOG; i++) if (bit(O, i) && (!bit(A, i))) B.push_back(i);
    int log = B.size();
    if (log > 18) assert(0);
    for (int i = 0; i < n; i++) {
        for (int j = log - 1; j >= 0; j--) a[i] = (a[i]<<1) | bit(vec[i], B[j]);
        memset(dp, 0, sizeof dp), cnt[0]++;
        for (int mask = 1; mask < (1<<log); mask++) {
            int b = __builtin_ctz(mask);
            dp[mask] = dp[mask^(1<<b)] + pw[b] * (bit(a[i], b) + 1);
            cnt[dp[mask]]++;
        }
    }
    BT(log - 1, 0, 0);
    cout << ans << "\n";
}