Background

Legend says that the reason this day is called “Flower Goddess’s Birthday” is that it originally meant “celebrating the Flower Goddess.”

A long, long time ago, the Tree King (Lady) had a birthday. Her friends held a banquet to celebrate it.

At the banquet, several gods got drunk. One of them, in high spirits, started playing an instrument. Then the Tree King began to sing, and the Flower Goddess started to dance.

As the Flower Goddess danced, countless beautiful Patishalan grew on the grass she stepped on...

Ah, if only time could stay at that moment forever.

Problem Description

You are preparing a banquet for the Flower Goddess’s Birthday. You have $N$ kinds of ingredients, numbered $1,2,\cdots,N$ in order. The flavor of ingredient $i$ is $a_i$, and the flavors of any two ingredients are all different. You want to use these $N$ ingredients to make two dishes. Each ingredient must be used in exactly one dish. Each dish must use at least one ingredient.

In the same dish, the flavors of different ingredients will react pairwise. If ingredient $i$ reacts with ingredient $j$, it produces a flavor of $a_i \oplus a_j$, where $\oplus$ denotes the XOR operation. The final flavor of a dish is the minimum among all flavors produced by these pairwise reactions. For example, if a dish uses three ingredients with flavors $2,3,4$, then the pairwise reactions produce three flavors: $1(2 \oplus 3)$, $6(2 \oplus 4)$, and $7(3 \oplus 4)$. The flavor of this dish is $\min(1,6,7)=1$.

The “original” flavor is the most delicious. If a dish uses only one ingredient, then the flavor of this dish is $+\infty$.

You want the flavor of the first dish to be at least $k_1$, and the flavor of the second dish to be at least $k_2$. How many different cooking plans are there?

Note: using the same set of ingredients but swapping which one is the first dish and which one is the second dish counts as two different plans. For example, “dish 1 uses ingredients $1,2,3$ and dish 2 uses $4,5$” and “dish 1 uses $4,5$ and dish 2 uses $1,2,3$” are considered two different plans.

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

Input Format

The input has two lines.

The first line contains three positive integers $N,k_1,k_2$, representing the number of ingredient types, and the required flavor thresholds for the first and second dish.

The second line contains $N$ positive integers $a_1,a_2,\cdots,a_N$, where $a_i$ is the flavor of ingredient $i$.

Output Format

Output one line with one integer, representing the number of cooking plans modulo $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

Sample Explanation 2

The five cooking plans are listed below:

• Dish 1 uses ingredients $1,2,3$, and dish 2 uses ingredient $4$.
• Dish 1 uses ingredients $1,2$, and dish 2 uses ingredients $3,4$.
• Dish 1 uses ingredients $1,3$, and dish 2 uses ingredients $2,4$.
• Dish 1 uses ingredients $2,3,4$, and dish 2 uses ingredient $1$.
• Dish 1 uses ingredients $3,4$, and dish 2 uses ingredients $1,2$.

Subtasks

For all testdata, 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: it is guaranteed that $k_1=k_2$.

Special Property B: it is guaranteed that $k_1=1$.

Translated by ChatGPT 5