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;
using P = pair<int, int>;
const int M = 1000000007;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n, k, s, t;
    cin >> n >> k >> s >> t;
    if ((s | t) != t) {
        cout << 0 << '\n';
        return 0;
    }
    vector<int> a;
    for (int i = 0; i < n; ++i) {
        int aa;
        cin >> aa;
        if ((aa & s) == s && (aa | t) == t) {
            a.push_back(aa);
        }
    }
    n = a.size();
    k = min(n, k);
    vector<P> cond;
    for (int i = 0; i < 18; ++i) {
        if (((s >> i) & 1) == 0) {
            cond.push_back({ i, 0 });
        }
        if (((t >> i) & 1) == 1) {
            cond.push_back({ i, 1 });
        }
    }
    vector<unordered_map<long long, long long>> dp(k + 1);
    for (int i = 0; i <= k; ++i) {
        dp[i].reserve(1 << 20);
    }
    dp[0][0] = 1;
    for (int i = 0; i < n; ++i) {
        long long mask = 0;
        for (int j = 0; j < (int)cond.size(); ++j) {
            if (((a[i] >> cond[j].first) & 1) == cond[j].second) {
                mask ^= 1LL << j;
            }
        }
        for (int j = k - 1; j >= 0; --j) {
            for (auto& l : dp[j]) {
                dp[j + 1][l.first | mask] += l.second;
            }
        }
    }
    long long ans = 0;
    for (auto& i : dp) {
        ans += i[(1LL << (int)cond.size()) - 1];
    }

    cout << ans << '\n';

    return 0;
}