Papanași 是有史以来最棒的甜点，只有亲口尝过才能想象它的美味。它们是传统的罗马尼亚油炸或水煮甜甜圈，由软奶酪制成，趁热搭配酸奶油和甜浆果（通常是蓝莓）果酱食用——这是一种浓郁、蓬松且令人沉溺的甜点。

在你的生日那天，你想给每个人送上 Papanași 作为甜点。Papanași 有很多种类型。你收集了关于每位宾客喜好的一些信息。对于每位宾客 $i$，你已知他们喜欢的 Papanași 类型集合 $a_i$，表示为一个位掩码（bitmask）：一个包含非负整数元素的集合 $\{v_1, \dots, v_k\}$ 被写成数字 $2^{v_1} + \dots + 2^{v_k}$。

设 $x_i$ 为第 $i$ 位宾客分到的 Papanași 类型集合（表示为一个位掩码）。为了让一切都完美，你需要确保满足以下约束条件：

1. 存在一个 Papanași 类型集合 $s$（表示为一个位掩码）。$s$ 中的每种 Papanași 类型都应至少提供给一位宾客，而不在 $s$ 中的任何类型都不应提供。形式化地，$x_1 \text{ OR } x_2 \text{ OR } \dots \text{ OR } x_n = s$。
2. 存在一个 Papanași 类型集合 $t$（表示为一个位掩码）。$t$ 中的每种 Papanași 类型都应提供给奇数个宾客（这个要求是在梦中向你启示的，所以你必须遵守它以使梦想成真）。形式化地，$x_1 \text{ XOR } x_2 \text{ XOR } \dots \text{ XOR } x_n = t$。
3. 每位宾客分到的 Papanași 类型应至少包含他们喜欢的所有类型。形式化地，$a_i \subseteq x_i$。

由于你的生日快到了，你想用一道题来取悦自己。在遵守上述规则的前提下，有多少种不同的分法？如果某位宾客 $i$ 获得了不同的集合 $x_i$，则两种分法被认为是不同的。即使答案中包含某些人没有分到任何 Papanași 的方案也是可以的（虽然这在派对上不太合适）。由于这个数量可能非常大，你需要将其对 $10^9+7$ 取模。

输入格式

第一行包含三个整数：$n$、$s$ 和 $t$（$1 \le n \le 10^5$，$0 \le s, t \le 2^{30} - 1$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le s$）。

输出格式

输出一个整数：表示在模 $10^9 + 7$ 意义下，有多少种分法可以满足所有人的要求。

样例

输入样例 1

3 11 10
8 2 0

输出样例 1

12

输入样例 2

3 7 5
2 3 6

输出样例 2

0

输入样例 3

10 31 24
5 17 1 6 0 30 12 15 8 23

输出样例 3

8388608