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;

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
typedef double DOUBLE;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1
#define j0 gray_cat_j0

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const ll LL_INF = 1e17 + 16;
const int INF = 1e9 + 10;
const ll MOD = 1e9 + 7;

const int MAXN = 55, MAXB = 18;

vi v;

ll c[MAXN][MAXN];

int bit_cnt[1 << MAXB];

void solve(){
	int n, m, s, t;
	cin >> n >> m >> s >> t;
	if ((s & t) != s) {
		printf("0\n");
		return;
	}
	REP(i, 0, n) {
		int a;
		cin >> a;
		if ((t | a) == t && (s & a) == s) {
			v.pb(a);
		}
	}
	n = SZ(v);
	
	REPN(i, 0, n) {
		c[i][0] = c[i][i] = 1;
		REP(j, 1, i) {
			c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
		}
	}
	REP(i, 1, 1 << MAXB) {
		bit_cnt[i] = bit_cnt[i >> 1] + (i & 1);
	}
	
	ll ans = 0ll;
	REP(i, 0, n) {
		int mask_all = (s ^ t);
		for(int k = mask_all; ; k = (k - 1) & mask_all) {
			int cnt_allowed = n - 1 - i;
			REP(l, i + 1, n) {
				if ((v[i] ^ v[l]) & k) {
					cnt_allowed--;
				}
			}
			ll sgn = (bit_cnt[k] & 1) ? -1 : 1;
			REP(l, 0, m) {
				ans += sgn * c[cnt_allowed][l];
			}
			if (!k) {
				break;
			}
		}
	}
	cout << ans << endl;
}

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}