AND and OR

You are given $N$ numbers. You may perform the following operation any number of times.

• Choose two numbers and replace them with two non-negative integers whose bitwise AND and bitwise OR both equal those of the two chosen numbers.

After performing operations, you want to minimize the product of the numbers. Find the minimized product of the $N$ numbers. Since the product can be very large, output its remainder modulo $10^{9} + 7$ instead.

See the Hint section for an explanation of bitwise AND and bitwise OR.

The first line contains an integer $N$ between $2$ and $300\,000$.

The second line contains $N$ positive integers separated by spaces. Each integer is less than $2^{30}$.

Print the remainder of the minimized product modulo $10^{9} + 7$ on the first line.

Note that you are not minimizing the remainder of the product modulo $\mathbf{10}^{\mathbf{9}} + \mathbf{7}$.

A bitwise operation applies the operation to each bit position.

For example, suppose we bitwise AND $28$ and $87$. First, write $28$ and $87$ in binary so the bits are clear.

Take the bit at each position in order, apply AND, and write the result below. For AND, the result is 1 only when both bits are 1; otherwise it is 0.

Bitwise OR works the same way. For OR, the result is 0 only when both bits are 0; otherwise it is 1.