题目背景

位掩码是一种非常强大的东西，常常用来过滤数据，现在你被小 k 给定了一个任务，你需要从一堆数字中求和，检查有哪些方案能够通过掩码测试

题目描述

给定一个长度为 $n$ 的正整数数组 $a$，以及两个整数 $A$ 和 $B$。 请你计算：从数组中选取任意个数（每个数只能选一次），设它们的和为 $S$，满足如下条件的方案数：

其中 & 表示按位与运算。

输入格式

第一行包含三个整数 $n,A,B$。（保证 $1 \leq n \leq 25$ ， $1 \leq A, B \leq 10^9$）

第二行包含 $n$ 个正整数，表示数组中的元素。（保证 $1 \leq a_i \leq 10^7$）

输出格式

一个整数，表示满足条件的方案总数。

样例

3 7 2
1 2 4

1

样例解释

数组为 $[1, 2, 4]$，$A=7, B=2$。我们需要 $(S \text{ \& } 7) = 2$。

1. 选取 $\{2\}$：$S=2$，$2 \text{ \& } 7 = 2$（符合）。
2. 选取 $\{2, 4\}$：$S=6$，$6 \text{ \& } 7 = 6 \neq 2$（不符）。
3. 选取 $\{1, 2, 4\}$：$S=7$，$7 \text{ \& } 7 = 7 \neq 2$（不符）。by软工25王凯龙