Gift or Poison?

In this problem, you are given a sequence \( a_1, a_2, \dots, a_n \) of integers. Your task is to count the number of nonincreasing subsequences of length at least 2 such that for every adjacent pair in the subsequence, the binomial coefficient modulo 2 is odd.

More formally, if you choose a subsequence with indices \( 1 \le b_1 < b_2 < \dots < b_k \le n \) (with \( k \ge 2 \)), then the subsequence \( a_{b_1}, a_{b_2}, \dots, a_{b_k} \) must satisfy:

\[ \prod_{i=2}^{k} \binom{a_{b_{i-1}}}{a_{b_i}} \bmod 2 > 0 \]

Because the product modulo 2 is odd if and only if each factor is odd, this condition is equivalent to demanding that for every adjacent pair \( (a_{b_{i-1}}, a_{b_i}) \):

\[ a_{b_{i-1}} \ge a_{b_i} \quad \text{and} \quad \binom{a_{b_{i-1}}}{a_{b_i}} \bmod 2 = 1. \]

It is a known fact (using Lucas' Theorem) that \( \binom{n}{m}\bmod2 = 1 \) if and only if the binary representation of \( m \) is a subset of the binary representation of \( n \) (i.e. every bit that is set in \( m \) is also set in \( n \)).

Since the number of subsequences can be huge, output your answer modulo \( 10^9+7 \).

Note: The input sequence is processed in the order given, so the indices in the subsequence must be strictly increasing.

Good luck and Vorsicht, Gift!

inputFormat

The first line contains a single integer \( n \) representing the length of the sequence.

The second line contains \( n \) space-separated integers \( a_1, a_2, \dots, a_n \).

outputFormat

Output a single integer: the number of valid nonincreasing subsequences (of length at least 2) satisfying the specified condition, taken modulo \( 10^9+7 \).

sample

3
1 1 1

4