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;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define mp make_pair
#define ld long double
typedef pair<int, int> pii;
typedef priority_queue<int, vector<int>, greater<int> > small_heap;
typedef priority_queue<int> big_heap;
const int N = 1e6 + 100;
int T;
int n, k, s, t;
int m, a[250];
ll c[250][250];
int cnt[1 << 18], vis[1 << 18];

ll calc(int x) {
    for (int i = 1; i <= n; i++) {
        ++cnt[a[i] & x];
    }
    ll tot = 0;
    for (int i = 1; i <= n; i++) {
        int cc = a[i] & x;
        if (vis[cc])continue;
        vis[cc] = 1;
        for (int j = 1; j <= k; ++j) {
            tot += c[cnt[cc]][j];
        }
    }
    for (int i = 1; i <= n; ++i) {
        vis[a[i] & x] = cnt[a[i] & x] = 0;
    }
    return tot;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> k >> s >> t;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        bool ok = true;
        for (int j = 0; j < 18; j++) {
            if ((s >> j) & 1 && !((x >> j) & 1) || !((t >> j) & 1) && (x >> j) & 1) {
                ok = false;
                break;
            }
        }
        if (ok)a[++m] = x;
    }

    for (int i = 0; i < 18; i++) {
        if (((s >> i) & 1) && (!(t >> i) & 1)) {
            puts("0");
            return 0;
        }
    }

    if (!n) {
        puts("0");
        return 0;
    }
    c[0][0] = 1;
    for (int i = 1; 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];
    }

    n = m;
    ll ans = 0;
    for (int i = s ^t;; i = (i - 1) & (s ^ t)) {
        ans += __builtin_popcount(i) & 1 ? -calc(i) : calc(i);
        if (!i)break;
    }
    cout << ans << endl;
    return 0;
}