[湖北省选模拟 2024] 花神诞日 / sabzeruz

传说，之所以这个日子会叫做「花神诞日」，其实最早是「花神祝诞」的意思。 在很久很久以前，有一次树王大人过生日，她的朋友们举办了宴席为她祝寿。 宴席上，几位神明大人都喝醉了，其中一位便乘兴弹奏起了乐器，于是树王大人唱歌，花神大人就跳起舞来。 在花神大人起舞时，她踏过的草地上，长出了无数美丽的帕蒂沙兰…… 啊，若是时间能永驻此刻就好了。

你正在为花神诞日准备宴席。你一共有 $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$ 取模的值。

输入共两行。 输入的第一行为三个正整数 $N,k_1,k_2$，分别表示食材的种类数、第一道菜与第二道菜要求的味道。 输入的第二行包含 $N$ 个正整数 $a_1,a_2,\cdots,a_N$，$a_i$ 表示第 $i$ 种食材的味道。

输出一行一个整数，表示做菜的方案数对 $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。

### 样例解释 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$。 | 测试点编号 | $N\le$ | 特殊性质 | | :--:|:--:|:--:| | $1$ | $18$ | 无 | | $2\sim 3$ | $5\times 10^3$ | A | | $4\sim 8$ | $5\times 10^3$ | 无 | | $9\sim 11$ | $2\times 10^5$ | A | | $12\sim 15$ | $2\times 10^5$ | B | | $16\sim 25$ | $2\times 10^5$ | 无 | 特殊性质 A：保证 $k_1=k_2$。 特殊性质 B：保证 $k_1=1$。