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 <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

const int N = 51;

ll C[N][N];

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  for (int i = 0; i < N; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
  }
  
  int n, k, s, t;
  cin >> n >> k >> s >> t;
  vector <int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  if (!((s & t) == s)) {
    cout << "0\n";
    return 0;
  }
  {
    vector <int> na;
    for (int i = 0; i < n; ++i) {
      if ((s & a[i]) == s && ((t | a[i]) == t)) {
        na.push_back(a[i]);
      }
    }
    a = na;
    n = a.size();
  }
  vector <int> bits;
  for (int i = 17; i >= 0; --i) {
    if ((s ^ t) & (1 << i)) {
      bits.push_back(i);
    }
  }
  int sz = (1 << (int)bits.size());
  for (int &x : a) {
    int y = 0;
    for (int i = 0; i < (int)bits.size(); ++i) {
      y = 2 * y + ((x >> bits[i]) & 1);
    }
    x = y;
  }
  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int mask = 0; mask < sz; ++mask) {
      int cnt = 0;
      for (int j = i + 1; j < n; ++j) {
        if (((a[i] ^ a[j]) & mask) == (a[i] ^ a[j])) ++cnt;
      }
      int s = (__builtin_popcount(mask) % 2 == __builtin_popcount(sz - 1) % 2 ? 1 : -1);
      for (int x = 0; x <= min(cnt, k - 1); ++x) {
        ans += s * C[cnt][x];
      }
    }
  } 
  cout << ans << '\n';
}