配点 : $800$ 点

問題文

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

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

制約

• $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$)

入力

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

$N$ $K$ $S$ $T$

$A_1$ $A_2$ $...$ $A_N$

出力

答えを出力せよ。

3 3 0 3
1 2 3

2

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

5 3 1 7
3 4 9 1 5

2

5 4 0 15
3 4 9 1 5

3