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 JAVA):

Solution:
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main {
    long[][] c = new long[51][51];

    void solve(Scanner sc, PrintWriter pw) {
        int N = sc.nextInt();
        int K = sc.nextInt();
        long S = sc.nextLong();
        long T = sc.nextLong();
        long[] data = new long[N];
        for (int i = 0; i < N; i++) {
            data[i] = sc.nextLong();
        }
        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];
            }
        }
        long[] sum = new long[(N + 1)];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= Math.min(i, K); j++) {
                sum[i] += c[i][j];
            }
        }
        long result = 0;
        List<Long> nums = new ArrayList<>();
        for (long mask = 0; mask < (1L << 18); mask++) {
            if (((T ^ S) & mask) != mask) {
                continue;
            }
            boolean isAdd = (Long.bitCount(mask) % 2) == 0;
            nums.clear();
            for (int i = 0; i < N; i++) {
                if ((data[i] & S) != S) {
                    continue;
                }
                if ((data[i] | T) != T) {
                    continue;
                }
                nums.add(data[i] & mask);
            }
            Collections.sort(nums);
            int begin = 0;
            int nextBegin;
            while (begin < nums.size()) {
                nextBegin = begin + 1;
                while (nextBegin< nums.size() && nums.get(nextBegin).equals(nums.get(nextBegin - 1))) {
                    nextBegin++;
                }
                result += (isAdd ? 1L : -1L) * (sum[nextBegin - begin]);
                begin = nextBegin;
            }
        }
        pw.println(String.format("%d", result));
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        new Main().solve(sc, pw);
        pw.flush();
        pw.close();
        sc.close();
    }
}