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;
typedef long long ll;
const int N=55;
int n,m,k,s,t,a[N],b[N],vis[N];
ll c[N][N];
int main()
{
    for(int i=1;i<N;i++)
        for(int j=0;j<=i;j++)
        if(j==0||j==i) c[i][j]=1;
        else if(j==1) c[i][j]=i;
        else c[i][j]=c[i-1][j-1]+c[i-1][j];
    for(int i=1;i<N;i++)
        for(int j=1;j<N;j++)
        c[i][j]+=c[i][j-1];
    scanf("%d%d%d%d",&n,&k,&s,&t);
    for(int i=1;i<=n;i++)
    {
        int x;scanf("%d",&x);
        if((s&x)==s&&(x&t)==x) a[++m]=x;
    }
    if(m==0){printf("0\n");return 0;}
    assert((s&t)==s);
    t-=s;
    if(t==0)
    {
        int sum=0;
        for(int i=1;i<=m;i++)
            sum+=a[i]==0;
        printf("%lld\n",c[sum][k]-1);
        return 0;
    }
    int l=__builtin_popcount(t);
    for(int i=0,j=0;i<18;i++)
        if(t>>i&1) vis[i]=++j;
    for(int i=1;i<=m;i++)
    {
        int x=0;
        for(int j=0;j<18;j++)
            if(vis[j]&&(a[i]>>j&1)) x|=1<<vis[j]-1;
        a[i]=x;
    }
    ll ans=0;
    for(int i=0;i<1<<l;i++)
    {
        ll res=0;
        for(int j=1;j<=m;j++)
            b[j]=a[j]&i;
        sort(b+1,b+1+m);
        int t=1;
        for(int j=2;j<=m;j++)
            if(b[j]==b[j-1]) t++;
        else res+=c[t][k]-1,t=1;
        res+=c[t][k]-1;
        if(__builtin_popcount(i)&1) ans-=res;
        else ans+=res;
    }
    printf("%lld\n",ans);
}