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;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    unsigned n,k,s,t,a;
    cin>>n>>k>>s>>t;
    vector<unsigned> A,c;
    fr(i,n){
        cin>>a;
        if((a&s)==s and (a|t)==t) A.push_back(a);
    }
    n=A.size();
    chmin(k,n);
    c.resize(n);
    unsigned l{};
    for(unsigned i{};i<18u;++i){
        if((s>>i)&1u) continue;
        if((t>>i)&1u){
            fr(j,n) c[j]^=((A[j]>>i)&1u)<<l;
            ++l;
        }
    }
    ll comb[51][51]={};
    fr(i,n+1){
        comb[i][0]=comb[i][i]=1;
        Fr(j,i-1) comb[i][j]=comb[i-1][j-1]+comb[i-1][j];
    }
    vector<ll> K(n+1);
    Fr(i,n) Fr(j,k) K[i]+=comb[i][j];
    ll ans{};
    fr(b,1u<<l){
        ll tmp{};
        map<ll,int> mp;
        fr(i,n) ++mp[c[i]&b];
        for(auto[key,val]:mp) tmp+=K[val];
        if(__builtin_popcount(b)&1u) ans-=tmp;
        else ans+=tmp;
    }
    cout<<ans<<'\n';
}