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;

const int M = 18;
int S, T, nr, N0, N, K, a[60], cnt[(1 << M) + 10];
long long c[60][60], atMostK[60];

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d %d %d", &N0, &K, &S, &T);
if ((T & S) != S)
{
    printf ("0\n");
    return 0;
}
for (int i=0; i<=N0; i++)
{
    c[i][0] = 1;
    for (int j=1; j<=i; j++)
        c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
for (int i=0; i<M; i++)
    nr += (((S ^ T) >> i) & 1);
for (int i=1; i<=N0; i++)
{
    int a0;
    scanf ("%d", &a0);
    if ((a0 & S) == S && (a0 | T) == T)
    {
        int a1 = 0, pos = 0;
        for (int j=0; j<M; j++)
            if ((S ^ T) & (1 << j))
            {
                if (a0 & (1 << j))
                    a1 |= 1 << pos;
                pos ++;
            }
        a[++N] = a1;
    }
}
for (int i=0; i<=N; i++)
    for (int j=1; j<=K && j<=i; j++)
        atMostK[i] += c[i][j];
///I want to choose between 1 and K elements in a s.t. their or is 1 << nr - 1 and their and is 0
long long ans = 0;
for (int msk = 0; msk < (1 << nr); msk ++)
{
    int sg = 0;
    for (int i=0; i<M; i++)
        if (msk & (1 << i))
            sg ^= 1;
    long long curr = 0;
    for (int i=1; i<=N; i++)
    {
        curr -= atMostK[cnt[a[i] & msk]];
        cnt[a[i] & msk] ++;
        curr += atMostK[cnt[a[i] & msk]];
    }
    if (sg)
        ans -= curr;
    else
        ans += curr;
    for (int i=1; i<=N; i++)
        cnt[a[i] & msk] = 0;
}
printf ("%lld\n", ans);
return 0;
}