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 i64 = int64_t;
template <class T> using Vec = std::vector<T>;
template <class K, class V> using UM = std::unordered_map<K, V>;

using namespace std;

namespace std {
template <>
struct hash<pair<int, int>> {
    size_t operator()(pair<int,int> p) const noexcept {
        return (size_t(p.first) << 18) | (size_t(p.second));
    }
};
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k, s, t;
    cin >> n >> k >> s >> t;

    Vec<int> as(n);
    for (auto &a : as) cin >> a;

    if ((s & t) != s || (s | t) != t) {
        cout << 0;
        return 0;
    }

    auto invalid = [&](int a) {
        return s != (s & a) || t != (t | a);
    };
    as.erase(remove_if(as.begin(), as.end(), invalid), as.end());

    n = as.size();

    Vec<UM<pair<int, int>, i64>> by_andor(k + 19);
    by_andor[0][{t, s}] = 1;

    for (auto &lvl : by_andor) lvl.reserve(1 << 18);
    int aand, oor;

    for (int i = 0; i < as.size(); ++i) {
        int a = as[i];

        for (int j = min(i, k - 1); j >= 0; --j) {
            auto &next = by_andor[j + 1];

            for (auto &[key, value] : by_andor[j]) {
                tie(aand, oor) = key;
                next[{aand & a, oor | a}] += value;
            }
        }
    }

    i64 ans = 0;
    for (int i = 0; i <= k; ++i) ans += by_andor[i][{s, t}];
    cout << ans << '\n';

    return 0;
}