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;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';


template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}

//INSERT ABOVE HERE
const Int LOG = 18;
const Int SZ = 1<<LOG;
using ll = long long;
ll dp[SZ]={};
ll binom[55][55];
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  binom[0][0]=1;
  for(Int i=0;i<52;i++){
    for(Int j=0;j<52;j++){
      binom[i+1][j+0]+=binom[i][j];
      binom[i+1][j+1]+=binom[i][j];
    }
  }

  Int n,k,s,t;
  cin>>n>>k>>s>>t;

  vector<Int> as;
  for(Int i=0;i<n;i++){
    Int a;
    cin>>a;
    if((a&s)!=s) continue;
    if((a|t)!=t) continue;
    as.emplace_back(a);
  }
  if(as.empty()) drop(0);
  n=as.size();

  ll ans=0;
  for(Int p=0;p<n;p++){
    Int b=as[p];

    memset(dp,0,sizeof(dp));
    for(Int q=p+1;q<n;q++){
      Int a=as[q];

      Int ok=0;

      for(Int j=0;j<LOG;j++){
        if(((s>>j)&1)==((t>>j)&1)) ok|=1<<j;
        if(((a>>j)&1)!=((b>>j)&1)) ok|=1<<j;
      }
      dp[ok]++;
    }

    for(Int i=1;i<SZ;i<<=1)
      for(Int j=0;j<SZ;j++)
        if((j&i)==0) dp[j|i]+=dp[j];

    for(Int bit=0;bit<SZ;bit++){
      Int ng=LOG-__builtin_popcount(bit);
      for(Int c=0;c<k;c++){
        if(ng&1) ans-=binom[dp[bit]][c];
        else ans+=binom[dp[bit]][c];
      }
    }
  }
  cout<<ans<<newl;
  return 0;
}