Description

你正在为花神诞日准备宴席。你一共有 $N$ 种食材，依次编号为 $1,2,\cdots, N$，第 $i$ 种食材的味道为 $a_i$，任意两种食材的味道都不相同。你希望用这 $N$ 种食材做两道菜，每种食材必须被在恰好一道菜中使用。每道菜至少使用一种食材。

同一道菜中不同食材的味道会两两发生反应。食材 $i$ 与食材 $j$ 反应，将产生 $a_i \oplus a_j$ 的味道，其中 $\oplus$ 表示异或运算。一道菜最终的味道为两两反应产生的味道的最小值。例如，一道菜使用了味道分别为 $2,3,4$ 的三种食材，食材将会两两反应产生 $1(2 \oplus 3)$，$6(2\oplus 4)$，$7(3\oplus 4)$ 三种味道，这道菜的味道为 $\min(1,6,7)=1$。

本真的味道最为美味。如果一道菜只使用了一种食材，这道菜的味道为 $+\infty$。

你希望第一道菜的味道不低于 $k_1$，第二道菜的味道不低于 $k_2$。请问，你一共有多少种做菜的方案？

请注意：相同集合的食材，分别作为第一道菜与第二道菜是两种不同的方案。 例如，第一道菜使用食材 $1,2,3$，第二道菜使用食材 $4,5$，与第一道菜使用食材 $4,5$，第二道菜使用食材 $1,2,3$ 是两种不同的方案。

由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模的值。

Input Format

输入共两行。

输入的第一行为三个正整数 $N,k_1,k_2$，分别表示食材的种类数、第一道菜与第二道菜要求的味道。

输入的第二行包含 $N$ 个正整数 $a_1,a_2,\cdots,a_N$，$a_i$ 表示第 $i$ 种食材的味道。

Output Format

输出一行一个整数，表示做菜的方案数对 $10^9+7$ 取模的结果。

2 10 10
1 2

2

4 2 5
5 3 1 4

5

见选手目录下的 sabzeruz/sabzeruz3.in 与 sabzeruz/sabzeruz3.ans。

该样例符合测试点 9 ∼ 11 的限制。

见选手目录下的 sabzeruz/sabzeruz4.in 与 sabzeruz/sabzeruz4.ans。

该样例符合测试点 12 ∼ 15 的限制。

见选手目录下的 sabzeruz/sabzeruz5.in 与 sabzeruz/sabzeruz5.ans。

Hint

样例解释 2

做菜的五种方式列举如下：

• 第一道菜使用食材 $1,2,3$，第二道菜使用食材 $4$。
• 第一道菜使用食材 $1,2$，第二道菜使用食材 $3,4$。
• 第一道菜使用食材 $1,3$，第二道菜使用食材 $2,4$。
• 第一道菜使用食材 $2,3,4$，第二道菜使用食材 $1$。
• 第一道菜使用食材 $3,4$，第二道菜使用食材 $1,2$。

子任务

对于所有测试数据，保证 $1 \le N \le 2\times 10^5$，$1 \le k_1,k_2,a_i <2^{60}$。对于任意的 $1 \le i<j \le N$，有 $a_i \neq a_j$。

特殊性质 A：保证 $k_1=k_2$。

特殊性质 B：保证 $k_1=1$。