Description

A simple problem, both a gift and a poison.

B designed a simple problem to give as a "gift" to everyone.

Given a sequence of length $n$, $a_1, a_2, \cdots , a_n$, ask how many non-increasing subsequences of length at least $2$ satisfy:

$$\prod _{i=2}^{k} \binom{a_{b_{i-1}}}{a_{b_i}} \bmod 2 = \binom{a_{b_1}}{a_{b_2}} \times \binom{a_{b_2}}{a_{b_3}} \times \cdots \binom{a_{b_{k-1}}}{a_{b_k}} \bmod 2 > 0$$

Output this count modulo $1000000007$.

G, after seeing the problem, explained some basic concepts for everyone.

We choose any number of integers $b_i$ satisfying

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

We call $a_{b_1}, a_{b_2}, \cdots, a_{b_k}$ a subsequence of $a$.

If this subsequence also satisfies

$$a_{b_1} \geq a_{b_2} \geq \cdots \geq a_{b_{k-1}}\geq a_{b_k}$$

we call the subsequence non-increasing.

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

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

Note in particular that since we only consider non-increasing subsequences, it must hold during binomial computation that $n \geq m$, i.e., in $\binom {a_{b_{i-1}}}{a_{b_i}}$ we always have $a_{b_{i-1}} \geq a_{b_i}$.

We emphasize the definition of $x \mod y$: $x \bmod y = x -\left \lfloor \frac{x}{y} \right \rfloor \times y$ where $\left \lfloor n \right \rfloor$ denotes the greatest integer less than or equal to $n$.

$x \bmod 2 > 0$ means that $x$ is odd.

Meanwhile, experience tells us that a sequence of length $n$ has $O(2^n)$ subsequences, so we take the answer modulo to avoid an overly large output.

B felt that G’s points were very reasonable and reiterated these basics.

Finally, upon hearing that this problem is a "gift" to everyone, G had a piece of advice.

“Vorsicht, Gift!”

“Careful... highly toxic!”

Input Format

The first line contains an integer $n$.

Then follow $n$ lines, each containing one integer. The $i$-th of these $n$ lines is $a_i$.

Output Format

Output a single integer, the answer.

4
15
7
3
1

11

Hint

For the first $10\%$ of the test points, $n \leq 9$, $1\leq a_i\leq 13$.

For the first $20\%$ of the test points, $n\leq 17$, $1\leq a_i\leq 20$.

For the first $40\%$ of the test points, $n\leq 1911$, $1\leq a_i\leq 4000$.

For the first $70\%$ of the test points, $n\leq 2017$.

For the first $85\%$ of the test points, $n\leq 100084$.

For $100\%$ of the test points, $1\leq n\leq 211985$, $1\leq a_i\leq 233333$. All $a_i$ are pairwise distinct, that is, there do not exist $i, j$ such that $1\leq i < j\leq n$ and $a_i = a_j$.

Translated by ChatGPT 5