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>
#define rep(i,l,r) for (int i=l;i<=r;++i)
#define per(i,r,l) for (int i=r;i>=l;--i)
#define rep0(i,r) for (int i=0;i<r;++i)
#define pr pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define ll long long
using namespace std;
const int N=2e6+6;
int tags[N],tagt[N],bit[N],a[N],b[N];
ll C[102][102],f[N]; bool del[N];
void solve(int t,int len){
    rep(i,1,len) f[i]+=t*C[len][i];
}
int main(){
    int n,k,s,t; cin>>n>>k>>s>>t;
    rep(i,0,n){
        C[i][0]=1;
        rep(j,1,i) C[i][j]=C[i-1][j]+C[i-1][j-1];
    }
    rep(i,1,n) cin>>a[i];
    rep(j,0,17) if (s>>j&1) tags[j]=1;
    rep(j,0,17) if (!(t>>j&1)) tagt[j]=1;
    int c=0;
    rep(j,0,17){
        if (tags[j]&&tagt[j]){
            cout<<0<<endl;
            return 0;
        }
        if (!tags[j]&&!tagt[j]) bit[++c]=j;
        if (tags[j])
            rep(i,1,n)
                if (!(a[i]>>j&1)) del[i]=true;
        if (tagt[j])
            rep(i,1,n)
                if (a[i]>>j&1) del[i]=true;
    }
    int _n=0;
    rep(i,1,n) if (!del[i]) a[++_n]=a[i];
    n=_n;
    rep(s,0,(1<<c)-1){
        int t=1; rep(i,1,c) if (s>>i-1&1) t=-t;
        rep(i,1,n){
            b[i]=0;
            rep(j,1,c)
                if ((s>>j-1&1)&&(a[i]>>bit[j]&1))
                    b[i]|=1<<j-1;
        }
        sort(b+1,b+1+n);
        int len=0;
        rep(i,1,n){
            if (i!=1&&b[i]!=b[i-1]) solve(t,len),len=0;
            ++len;
        }
        solve(t,len);
    }
    ll ans=0;
    rep(i,1,k) ans+=f[i];
    cout<<ans<<endl;
    return 0;
}