Dividing Ingredients for the Flower God Feast

You are preparing a banquet for the Flower God Birthday. You have (N) different ingredients, numbered (1,2,\dots,N). The (i)\textsuperscript{th} ingredient has a flavor value (a_i) and all (a_i) are distinct. You plan to make two dishes using these ingredients such that each ingredient is used in exactly one dish, and each dish uses at least one ingredient.

When two different ingredients with flavor values (a_i) and (a_j) are used in the same dish, they react and produce a new flavor of (a_i \oplus a_j) (where (\oplus) denotes the bitwise XOR operation). The overall flavor of a dish containing at least two ingredients is defined as the minimum over all pairwise reactions, i.e., [ \min_{\substack{i,j \in S\ i<j}} (a_i \oplus a_j). ] If a dish uses only one ingredient, its flavor is defined to be (+\infty) (which is considered higher than any finite threshold).

You are given two thresholds (k_1) and (k_2). The first dish must have a flavor not less than (k_1) and the second dish must have a flavor not less than (k_2). Two assignments are considered different if the set of ingredients chosen for the first dish differs (note that swapping the two dishes counts as a different scheme).

Determine the number of ways to partition the ingredients into two nonempty dishes satisfying the respective flavor constraints. Since the answer might be large, output it modulo (10^9+7).

inputFormat

The first line contains three integers (N), (k_1), and (k_2) (the number of ingredients and the flavor thresholds for the first and second dishes respectively).
The second line contains (N) space‐separated integers (a_1, a_2, \ldots, a_N), representing the flavor values of the ingredients.

outputFormat

Output a single integer: the number of valid ways to partition the ingredients into two dishes satisfying the conditions, modulo (10^9+7).

sample

3 1 1
2 3 4

6