P3773 [CTSC2017] Gift

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!”

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 a single integer, the answer.

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