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 <cstdio>
#include <vector>

using namespace std;

int a[50];
int b[18];
long long c[51][51];
long long d[51];

int main() {
    int n, k, s, t, i, j, l;
    long long ans = 0;
    vector<int> v, w;
    
    scanf("%d %d %d %d", &n, &k, &s, &t);
    
    for (i = 0; i < n; i++) scanf("%d", &a[i]);
    
    for (i = 0; i <= 50; i++) {
        c[i][0] = c[i][i] = 1;
        for (j = 1; j < i; j++) c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
    
    if (s == t) {
        for (i = 0; i < n; i++) {
            if (a[i] == s) {
                puts("1");
                
                return 0;
            }
        }
        
        puts("0");
        
        return 0;
    }
    
    for (i = 0; i < 18; i++) {
        if (((s >> i) & 1) == 1 && ((t >> i) & 1) == 0) {
            puts("0");
            
            return 0;
        }
        
        if ((s >> i) & 1) {
            b[i] = 0;
        } else if ((t >> i) & 1) {
            b[i] = 1;
            w.push_back(i);
        } else {
            b[i] = 2;
        }
    }
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < 18; j++) {
            if ((a[i] >> j) & 1) {
                if (b[j] == 2) break;
            } else {
                if (b[j] == 0) break;
            }
        }
        
        if (j == 18) v.push_back(a[i]);
    }
    
    for (i = 0; i <= n; i++) {
        for (j = 1; j < k && j <= i; j++) d[i] += c[i][j];
    }
    
    for (i = 0; i < v.size(); i++) {
        for (j = 0; j < (1 << w.size()); j++) {
            int x = 0, c = 0;
            
            for (l = 0; l < w.size(); l++) {
                if ((j >> l) & 1) x |= (1 << w[l]);
            }
            
            for (l = i + 1; l < v.size(); l++) {
                if (((~(v[i] ^ v[l])) & x) == x) c++;
            }
            
            if (__builtin_popcount(j) % 2 == 0) {
                ans += d[c];
            } else {
                ans -= d[c];
            }
        }
    }
    
    printf("%lld\n", ans);
    
    return 0;
}