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 <bits/stdc++.h>

using namespace std;

int main() {
    int N, K, S, T;
    cin >> N >> K >> S >> T;

    vector<map<pair<int,int>,long long>> dp(K+1);
    dp[0][{(1<<18)-1, 0}] = 1;

    for (int i = 0; i < N; ++i) {
        int a; cin >> a;
        if ((a & S) != S) continue;
        if ((a | T) != T) continue;
        for (int k = K-1; k >= 0; --k) {
            for (auto& p : dp[k]) {
                int prod, sum; tie(prod, sum) = p.first;
                dp[k+1][{prod & a, sum | a}] += p.second;
            }
        }
    }

    long long ans = 0;
    for (int k = 1; k <= K; ++k) {
        ans += dp[k][{S, T}];
    }
    cout << ans << endl;

    return 0;
}
