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;
const int N=300005;
const long long M=998244353;
const long long iv2=499122177;
int n,k,s,t,a[55],f[N],i,j,id[55],b[55],p;
long long dp[N],C[55][55],ans;
int main()
{
	scanf("%d %d %d %d",&n,&k,&s,&t);
	for(j=0;j<18;++j)
		if(((s>>j)&1)&&(!((t>>j)&1)))
		{
			puts("0");
			return 0;
		}
	for(i=0;i<=50;++i)
	{
		C[i][0]=C[i][i]=1;
		for(j=1;j<i;++j)
			C[i][j]=C[i-1][j]+C[i-1][j-1];
	}
	memset(id,-1,sizeof(id));
	int y=0;
	for(j=0;j<18;++j)
		if((!((s>>j)&1))&&((t>>j)&1))
			id[j]=y++;
	for(i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		if((a[i]&s)==s&&((a[i]|t)==t))
		{
			++p;
			for(j=0;j<18;++j)
				if(((a[i]>>j)&1)&&id[j]!=-1)
					b[p]|=1<<id[j];
		}
	}
	--k;
	for(int u=1;u<=p;++u)
	{
		memset(f,0,sizeof(f));
		memset(dp,0,sizeof(dp));
		for(i=u+1;i<=p;++i)
		{
			int s=0;
			for(j=0;j<y;++j)
				if(((b[i]>>j)&1)!=((b[u]>>j)&1))
					s|=1<<j;
			++f[s];
		}
		for(i=0;i<y;++i)
			for(j=0;j<(1<<y);++j)
				if((j>>i)&1)
					f[j]+=f[j^(1<<i)];
		for(i=0;i<(1<<y);++i)
			for(j=0;j<=k;++j)
				dp[i]+=C[f[i]][j];
		for(i=0;i<y;++i)
			for(j=0;j<(1<<y);++j)
				if((j>>i)&1)
					dp[j]-=dp[j^(1<<i)];
		ans+=dp[(1<<y)-1];
	}
	cout<<ans<<endl; 
}