A sequence of integers is said to be beautiful if the bitwise AND, OR, and XOR of its elements are pairwise equal to each other.

You are given a sequence \(A\) of size \(N\). Find the number of non-empty subsequences of \(A\) that are beautiful. Print the answer modulo \(10^9 + 7\).

Input format

• The first line contains an integer \(N\) representing the number of elements in the sequence.
• The second line contains \(N\) space-separated integers \(A_1,\ A_2,\ ...,\ A_N\) representing the sequence. 

Output format

In a single line, print the number of non-empty subsequences of \(A\) that are beautiful.

Constraints

\(1 \leq N \leq 2 \cdot 10^5\\ 0 \leq A_i \leq 10^{9}\)