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=50,M=262144,C=18;

int n,m,san,sor,a[N+9];

void into(){
  scanf("%d%d%d%d",&n,&m,&san,&sor);
  for (int i=1;i<=n;++i)
	scanf("%d",&a[i]);
}

void Get_a(){
  int lst=0;
  for (int i=1;i<=n;++i){
	if (a[i]&san^san) continue;
	if ((a[i]|sor)^sor) continue;
    a[++lst]=a[i];
  }
  n=lst;
}

LL c[N+9][N+9];

void Get_c(){
  c[0][0]=1;
  for (int i=1;i<=n;++i){
	c[i][0]=c[i][i]=1;
	for (int j=1;j<i;++j) c[i][j]=c[i-1][j-1]+c[i-1][j];
  }
}

int mu[M+9];

void Get_mu(){
  mu[0]=1;
  for (int s=1;s<M;++s) mu[s]=s&1?-mu[s>>1]:mu[s>>1];
}

int vis[M+9],cnt[M+9];
LL ans;

void Get_ans(){
  if (!n) return;
  for (int cs=san^sor,s=cs;2333;s=s-1&cs){
	for (int i=1;i<=n;++i) ++cnt[a[i]&s];
	for (int i=1;i<=n;++i){
	  int t=a[i]&s;
	  if (vis[t]) continue;
	  vis[t]=1;
	  for (int j=1;j<=m;++j) ans+=c[cnt[t]][j]*mu[s];
	}
	for (int i=1;i<=n;++i) vis[a[i]&s]=cnt[a[i]&s]=0;
	if (!s) break;
  }
}

void work(){
  Get_a();
  Get_c();
  Get_mu();
  Get_ans();
}

void outo(){
  printf("%lld\n",ans);
}

int main(){
  into();
  work();
  outo();
  return 0;
}