题目描述

给出一个长度为 $n$ 的非负整数序列 $a_1,a_2,\cdots,a_n$，这个数列元素互不相等。从中选出 $1\sim k$ 个数字，使它们按位与结果为 $S$，按位或结果为 $T$。求可选择的方案数。

输入格式

第一行四个整数 $n,k,S,T$。

第二行 $n$ 个非负整数，表示 $a_1,a_2,\cdots,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

数据范围

$1\le k \le n \le 50$，$0 \le a_i,S,T < 2^{18}$。