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 long long ll;
typedef pair <int, int> ii;

const int Maxb = 18;
const int Maxn = 51;

ll C[Maxn][Maxn];
ll ways[Maxn];
int n, k, s, t;
int a[Maxn];
vector <int> dif;
vector <ii> sam;
ll res;

void Gen(int lvl, int mask)
{
    if (lvl >= dif.size()) {
        ll cur = 0;
        for (int i = 0; i < n; i++) {
            int oth = 0;
            for (int j = i + 1; j < n; j++)
                if ((a[i] & mask) == (a[j] & mask)) oth++;
            cur += ways[oth];
        }
        if (__builtin_popcount(mask) % 2) res -= cur;
        else res += cur;
    } else {
        Gen(lvl + 1, mask);
        Gen(lvl + 1, mask | 1 << dif[lvl]);
    }
}

int main()
{
    for (int i = 0; i < Maxn; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
    cin >> n >> k >> s >> t;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < Maxn; i++)
        for (int j = 0; j < k; j++)
            ways[i] += C[i][j];
    for (int i = 0; i < Maxb; i++)
        if (bool(s & 1 << i) != bool(t & 1 << i))
            if (bool(s & 1 << i)) { printf("0\n"); return 0; }
            else dif.push_back(i);
        else sam.push_back(ii(i, int(bool(s & 1 << i))));
    int sz = 0;
    for (int i = 0; i < n; i++) {
        bool ok = true;
        for (int j = 0; j < sam.size() && ok; j++)
            ok = bool(a[i] & 1 << sam[j].first) == sam[j].second;
        if (ok) a[sz++] = a[i];
    }
    n = sz;
    Gen(0, 0);
    cout << res << endl;
    return 0;
}