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

Solution:
def popcount_parity(x):
    for i in range(8):
        x ^= x >> (1 << i)
    return -1 if x & 1 else 1

N, K, S, T = map(int, input().split())
if S & T != S:
    print(0)
    exit()

C = [[1]]
CC = [0] * 51
for i in range(1, 51):
    C.append([1] * (i + 1))
    for j in range(1, i):
        C[i][j] = C[i-1][j-1] + C[i-1][j]
for i in range(51):
    CC[i] = sum(C[i][1:K+1])

A = [int(a) for a in input().split()]
aa, oo = - 1, 0
for i in range(N)[::-1]:
    a = A[i]
    if a & S != S or a | T != T:
        del A[i]
        continue
    aa &= a
    oo |= a
aa ^= oo

i = aa
ans = 0
while 1:
    D = {}
    for a in A:
        t = i & a
        if t not in D: D[t] = 1
        else: D[t] += 1
    ans += sum([CC[t] for t in D.values()]) * popcount_parity(i)
    if not i: break
    i = (i - 1) & aa
print(ans)