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 <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, k, s, t;
    std::cin >> n >> k >> s >> t;
    std::vector<std::vector<long long>> C(n + 1, std::vector<long long>(n + 1));
    for (int i = 0; i <= n; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
    for (int i = 0; i <= n; ++i)
        for (int j = 2; j <= n; ++j)
            C[i][j] += C[i][j - 1];
    std::vector<int> a;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        if ((x & s) == s && (x | t) == t)
            a.push_back(x);
    }
    n = a.size();
    long long ans = 0;
    int c[1 << 18] = {};
    for (int v = 0; v < (1 << 18); ++v) {
        if ((v & s) != s || (v | t) != t)
            continue;
        long long res = 0;
        for (int i = 0; i < n; ++i)
            ++c[a[i] & v];
        for (int i = 0; i < n; ++i) {
            if (c[a[i] & v]) {
                res += C[c[a[i] & v]][k];
                c[a[i] & v] = 0;
            }
        }
        ans += (__builtin_parity(v ^ s) ? -1 : 1) * res;
    }
    std::cout << ans << "\n";
    return 0;
}