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;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=1000000007,MAX=205,INF=1<<30;

ll pat[MAX][MAX];

void make(){
    pat[0][0]=1;
    for(int i=1;i<=50;i++){
        for(int j=0;j<=i;j++){
            if(j) pat[i][j]+=pat[i-1][j-1];
            pat[i][j]+=pat[i-1][j];
        }
    }
}

ll comb(ll a,ll b){
    if(a<b) return 0;
    return pat[a][b];
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    make();
    
    int N,K,S,T;cin>>N>>K>>S>>T;
    
    if(S&(~T)){
        cout<<0<<endl;
        return 0;
    }
    vector<int> A;
    
    for(int i=0;i<N;i++){
        int a;cin>>a;
        
        if((S&a)!=S) continue;
        if((a|T)!=T) continue;
        
        A.push_back(a);
    }
    
    N=si(A);
    
    for(int a:A) a-=S;
    T-=S;
    S=0;
    
    vector<int> bi;
    for(int i=0;i<20;i++) if(T&(1<<i)) bi.push_back(i);
    for(int &a:A){
        int to=0;
        for(int i=0;i<si(bi);i++){
            if(a&(1<<bi[i])) to+=(1<<i);
        }
        a=to;
    }
    T=(1<<si(bi))-1;
    
    int L=si(bi);
    
    if(L==0){
        ll res=0;
        for(int j=1;j<=K;j++){
            res+=comb(N,j);
        }
        cout<<res<<endl;
        return 0;
    }
    
    if(K==1){
        cout<<0<<endl;
        return 0;
    }
    
    ll res=0;
    
    vector<ll> sum(L+1);
    
    for(int i=0;i<N;i++){
        for(int bit=0;bit<(1<<L);bit++){
            int cnt=0;
            for(int j=i+1;j<N;j++){
                if(((~(A[i]^A[j]))&bit)==bit) cnt++;
            }
            
            for(int j=0;j<K;j++){
                sum[__builtin_popcount(bit)]+=comb(cnt,j);
            }
        }
    }
    
    for(int j=0;j<=L;j++){
        if(j&1) res-=sum[j];
        else res+=sum[j];
    }
    
    cout<<res<<endl;
    
}