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>
#define ll long long
#define maxn 60

using namespace std;

int n,a[maxn],k;
int s,t;
ll sum[maxn],c[maxn][maxn];

int main() {
   // freopen("in.txt","r",stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin>>n>>k>>s>>t;
    for (int i=1;i<=n;i++) cin>>a[i];

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

    for (int i=1;i<=n;i++)
        for (int j=1;j<=min(i,k);j++) sum[i]+=c[j][i];

    ll ans = 0;
    for (int tt=0;tt<(1<<18);tt++)
        if ((tt&(s^t)) == tt) {
            //cout<<tt<<endl;
            int obit = 0;
            for (int i=0;i<18;i++) obit += (tt>>i)&1;

            vector<int> q;
            for (int i=1;i<=n;i++)
                if (((a[i]&s)==s) && ((a[i]|t)==t)) q.push_back(a[i]&tt);
            //cout<<q.size()<<endl;
            sort(q.begin(),q.end());
            int b=0,e=0;
            while (b<(int)q.size()) {
                e = b;
                while (e+1<(int)q.size() && q[e]==q[e+1]) e++;
                ans += (obit%2==0 ? 1 : -1) * sum[e-b+1];
                b = e+1;
            }
        }
    cout<<ans<<endl;
}