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
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll com[55][55];
ll rcom[55][55];
int zzz[55];
int main()
{
	int num, gen, lb, ub;
	scanf("%d%d%d%d", &num, &gen, &lb, &ub);
	vector<int>kets;
	for (int i = 0; i < 18; i++)if ((lb&(1 << i)) == 0 && (ub&(1 << i)) != 0)kets.push_back(i);
	vector<int>v;
	for (int i = 0; i < num; i++)
	{
		int z;
		scanf("%d", &z);
		if ((z&lb) != lb)continue;
		if ((z&ub) != z)continue;
		int x = 0;
		for (int j = 0; j < kets.size(); j++)
		{
			if (z&(1 << kets[j]))x += (1 << j);
		}
		v.push_back(x);
		//printf("%d %d\n",i, x);
	}
	int len = kets.size();
	num = v.size();
	for (int i = 0; i < 52; i++)
	{
		com[i][0] = 1;
		for (int j = 1; j <= i; j++)com[i][j] = com[i - 1][j - 1] + com[i - 1][j];
		for (int j = 1; j <= 52; j++)rcom[i][j] = rcom[i][j - 1] + com[i][j];
	}
	ll ans = 0;
	for (int p = 0; p < (1 << len); p++)
	{
		for (int i = 0; i < num; i++)zzz[i] = (p&v[i]);
		sort(zzz, zzz+num);
		zzz[num] = -1;
		ll t = 0;
		int c = 0, now = -1;
		for (int i = 0; i <= num; i++)
		{
			if (now != zzz[i])
			{
				t += rcom[c][min(c, gen)];
				now = zzz[i], c = 1;
			}
			else c++;
		}
		bool f = false;
		for (int i = 0; i < len; i++)if (p&(1 << i))f ^= 1;
		if (!f)ans += t;
		else ans -= t;
		//printf("  %d %lld\n", p, t);
	}
	printf("%lld\n", ans);
}