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>

const int N = 60;
const int BIT = 18;
using ll = long long;

int a[N];
ll comb[N][N];
ll precomb[N][N];
std::map <int, int> map[1 << BIT];

int main(){
    for (int i = 0; i < N; ++ i){
        comb[i][0] = 1;
        for (int j = 1; j <= i; ++ j){
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
        }
    }
    int n, k, s, t;
    scanf("%d%d%d%d", &n, &k, &s, &t);
    for (int i = 0; i < n; ++ i){
        scanf("%d", &a[i]);
    }
    if ((s & t) != s){
        puts("0");
        return 0;
    }
    std::vector <int> valid;
    for (int i = 0; i < n; ++ i){
        bool flag = true;
        for (int j = 0; j < BIT; ++ j){
            if ((a[i] >> j & 1) && !(s >> j & 1) && !(t >> j & 1)){
                flag = false;
                break;
            }
            if (!(a[i] >> j & 1) && (s >> j & 1) && (t >> j & 1)){
                flag = false;
                break;
            }
        }
        if (flag){
            valid.emplace_back(a[i]);
        }
    }
    int bit = 0;
    for (int i = 0; i < BIT; ++ i){
        if (!(s >> i & 1) && (t >> i & 1)){
            ++ bit;
        }
    }
    n = 0;
    for (auto u : valid){
        a[n] = 0;
        for (int i = BIT - 1; i >= 0; -- i){
            if (!(s >> i & 1) && (t >> i & 1)){
                a[n] = (a[n] << 1) | (u >> i & 1);
            }
        }
        ++ n;
    }
    for (int i = 0; i < n; ++ i){
        map[(1 << bit) - 1][a[i]] = 1;
    }
    for (int i = (1 << bit) - 2; i >= 0; -- i){
        int lb = (~i) & -(~i);
        for (auto p : map[i ^ lb]){
            map[i][p.first & (~lb)] += p.second;
        }
    }
    ll ans = 0;
    for (int i = 0; i < N; ++ i){
        for (int j = 1; j <= k; ++ j){
            precomb[i][j] = precomb[i][j - 1] + comb[i][j];
        }
    }
    for (int i = 0; i < 1 << bit; ++ i){
        for (auto p : map[i]){
            ans += (__builtin_popcount(i) & 1 ? -1 : 1) * precomb[p.second][k];
        }
    }
    printf("%lld\n", ans);
    return 0;
}