A simple problem can be both a gift and a poison.

Mr. B has designed a simple problem as a gift for everyone. Given a sequence $a_1, a_2, \dots, a_n$ of length $n$, how many non-increasing subsequences $a_{b_1}, a_{b_2}, \dots, a_{b_k}$ of length at least 2 satisfy:

$$\prod_{i=2}^{k} \binom{a_{b_{i-1}}}{a_{b_i}} \pmod 2 = \left( \binom{a_{b_1}}{a_{b_2}} \times \binom{a_{b_2}}{a_{b_3}} \times \dots \times \binom{a_{b_{k-1}}}{a_{b_k}} \right) \pmod 2 > 0$$

Output the result modulo $1000000007$.

Mr. G, after seeing the problem, explained some basic concepts. We choose any number of integers $b_i$ such that:

$$1 \le b_1 < b_2 < \dots < b_{k-1} < b_k \le n$$

We call $a_{b_1}, a_{b_2}, \dots, a_{b_k}$ a subsequence of $a$. If this subsequence also satisfies:

$$a_{b_1} \ge a_{b_2} \ge \dots \ge a_{b_{k-1}} \ge a_{b_k}$$

we call this subsequence non-increasing.

The binomial coefficient $\binom{n}{m}$ is the number of ways to choose $m$ elements from $n$ distinct elements, calculated as follows:

$$\binom{n}{m} = \frac{n!}{m!(n - m)!} = \frac{n \times (n - 1) \times \dots \times 2 \times 1}{(m \times (m - 1) \times \dots \times 2 \times 1)((n - m) \times (n - m - 1) \times \dots \times 2 \times 1)}$$

Note that since we only consider non-increasing subsequences, in the process of calculating the binomial coefficient, we must have $n \ge m$, which means in $\binom{a_{b_{i-1}}}{a_{b_i}}$, we always have $a_{b_{i-1}} \ge a_{b_i}$.

We emphasize the definition of the modulo operation $x \pmod y$:

$$x \pmod y = x - \left\lfloor \frac{x}{y} \right\rfloor \times y$$

where $\lfloor n \rfloor$ denotes the largest integer less than or equal to $n$. $x \pmod 2 > 0$ means that $x$ is an odd number.

Meanwhile, experience tells us that for a sequence of length $n$, there are $O(2^n)$ subsequences, so we take the result modulo a number to avoid an excessively large output.

Mr. B felt that Mr. G's explanation was very reasonable and reiterated these basic concepts. Finally, Mr. G heard that this problem was a gift for everyone and offered a piece of advice:

"Vorsicht, Gift!" "Careful... Poison!"

Input

The input is read from the file gift.in. The first line contains an integer $n$. The next $n$ lines each contain an integer, where the $i$-th line represents $a_i$.

Output

Output the result to the file gift.out. A single integer representing the answer.

Examples

Input 1

4
15
7
3
1

Output 1

11

Examples 2~9

See gift/gift2~9.in and gift/gift2~9.ans in the contestant directory.

Constraints

• For the first 10% of test cases, $n \le 9, 1 \le a_i \le 13$;
• For the first 20% of test cases, $n \le 17, 1 \le a_i \le 20$;
• For the first 40% of test cases, $n \le 1911, 1 \le a_i \le 4000$;
• For the first 70% of test cases, $n \le 2017$;
• For the first 85% of test cases, $n \le 100084$;
• For 100% of test cases, $1 \le n \le 211985, 1 \le a_i \le 233333$. All $a_i$ are distinct, meaning there do not exist $i, j$ such that $1 \le i < j \le n$ and $a_i = a_j$.