Problem Background

Legend has it that the day is called "Flower God's Birthday" because it originally meant "Flower God's Blessing for the Birthday."

A long, long time ago, when the Tree King celebrated her birthday, her friends held a banquet to wish her well.

At the banquet, several gods became drunk, and one of them, in high spirits, started playing an instrument. The Tree King sang, and the Flower God danced.

As the Flower God danced, the grass she stepped on sprouted countless beautiful Padisarans...

Ah, if only time could stop at this moment.

Problem Description

You are preparing for the Flower God's Birthday banquet. You have a total of \( N \) types of ingredients, numbered \( 1, 2, \cdots, N \), with the \( i \)-th ingredient having a flavor \( a_i \). No two ingredients have the same flavor. You want to use these \( N \) ingredients to make two dishes, with each ingredient used in exactly one dish. Each dish must use at least one ingredient.

Different ingredients in the same dish will react pairwise. The reaction between ingredient \( i \) and ingredient \( j \) will produce a flavor \( a_i \oplus a_j \), where \( \oplus \) denotes the XOR operation. The final flavor of a dish is the minimum of the flavors produced by these pairwise reactions. For example, if a dish uses three ingredients with flavors \( 2, 3, 4 \), the reactions will produce flavors \( 1 (2 \oplus 3) \), \( 6 (2 \oplus 4) \), and \( 7 (3 \oplus 4) \), and the flavor of the dish will be \( \min(1, 6, 7) = 1 \).

The most authentic flavor is the most delicious. If a dish uses only one ingredient, its flavor is \( +\infty \).

You want the flavor of the first dish to be no less than \( k_1 \), and the flavor of the second dish to be no less than \( k_2 \). How many different ways are there to prepare the dishes?

Note: The same set of ingredients, used as the first dish and the second dish, are considered different schemes. For example, using ingredients \( 1, 2, 3 \) for the first dish and ingredients \( 4, 5 \) for the second dish is different from using ingredients \( 4, 5 \) for the first dish and ingredients \( 1, 2, 3 \) for the second dish.

Since the answer may be very large, you only need to output the answer modulo \( 10^9 + 7 \).

Input Format

The input consists of two lines.

The first line contains three positive integers \( N, k_1, k_2 \), representing the number of ingredient types and the required flavors for the first and second dishes, respectively.

The second line contains \( N \) positive integers \( a_1, a_2, \cdots, a_N \), where \( a_i \) represents the flavor of the \( i \)-th ingredient.

Output Format

Output a single integer, which is the number of ways to prepare the dishes modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

2 10 10
1 2

Sample Output #1

2

Sample Input #2

4 2 5
5 3 1 4

Sample Output #2

5

Sample Input #3

See the file in the选手目录下的 sabzeruz/sabzeruz3.in and sabzeruz/sabzeruz3.ans.

Sample Output #3

This sample corresponds to test points 9 ∼ 11.

Sample Input #4

See the file in the选手目录下的 sabzeruz/sabzeruz4.in and sabzeruz/sabzeruz4.ans.

Sample Output #4

This sample corresponds to test points 12 ∼ 15.

Sample Input #5

See the file in the选手目录下的 sabzeruz/sabzeruz5.in and sabzeruz/sabzeruz5.ans.

Sample Output #5

Notes

Sample Explanation #2

The five ways to prepare the dishes are listed below:

• First dish uses ingredients \( 1, 2, 3 \), second dish uses ingredient \( 4 \).
• First dish uses ingredients \( 1, 2 \), second dish uses ingredients \( 3, 4 \).
• First dish uses ingredients \( 1, 3 \), second dish uses ingredients \( 2, 4 \).
• First dish uses ingredients \( 2, 3, 4 \), second dish uses ingredient \( 1 \).
• First dish uses ingredients \( 3, 4 \), second dish uses ingredients \( 1, 2 \).

Subtasks

For all test data, it is guaranteed that \( 1 \le N \le 2 \times 10^5 \), \( 1 \le k_1, k_2, a_i < 2^{60} \). For any \( 1 \le i < j \le N \), \( a_i \neq a_j \).

Special Property A: \( k_1 = k_2 \).

Special Property B: \( k_1 = 1 \).

见题面 Input 部分

见题面 Output 部分