题目描述

$N$ 個の相異なる非負整数 $A_1,A_2,\ldots,A_N$ が与えられます。 与えられた数の中から $1$ 個以上 $K$ 個以下の数を選ぶ方法であって、次の $2$ つの条件を満たすような方法は何通りあるか求めてください。

• 選ばれた数のビットごとの論理積は $S$ である。
• 選ばれた数のビットごとの論理和は $T$ である。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $S$ $T$ $A_1$ $A_2$ $...$ $A_N$

输出格式

答えを出力せよ。

题目大意

hhoppitree 有 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$，他想要从中选出至多 $k$ 个整数，使得它们的与为 $S$，或为 $T$，求方案数。

3 3 0 3
1 2 3

2

5 3 1 7
3 4 9 1 5

2

5 4 0 15
3 4 9 1 5

3

提示

制約

• $1\ \leqq\ N\ \leqq\ 50$
• $1\ \leqq\ K\ \leqq\ N$
• $0\ \leqq\ A_i\ <\ 2^{18}$
• $0\ \leqq\ S\ <\ 2^{18}$
• $0\ \leqq\ T\ <\ 2^{18}$
• $A_i\ \neq\ A_j$ ($1\ \leqq\ i\ <\ j\ \leqq\ N$)

Sample Explanation 1

$\{1,2\}$ もしくは $\{1,2,3\}$ と数を選ぶと条件を満たします。