CF1610D.Not Quite Lee

Lee couldn't sleep lately, because he had nightmares. In one of his nightmares (which was about an unbalanced global round), he decided to fight back and propose a problem below (which you should solve) to balance the round, hopefully setting him free from the nightmares.

A non-empty array $b_1, b_2, \ldots, b_m$ is called good, if there exist $m$ integer sequences which satisfy the following properties:

• The $i$-th sequence consists of $b_i$ consecutive integers (for example if $b_i = 3$ then the $i$-th sequence can be $(-1, 0, 1)$ or $(-5, -4, -3)$ but not $(0, -1, 1)$ or $(1, 2, 3, 4)$).
• Assuming the sum of integers in the $i$-th sequence is $sum_i$, we want $sum_1 + sum_2 + \ldots + sum_m$ to be equal to $0$.

You are given an array $a_1, a_2, \ldots, a_n$. It has $2^n - 1$ nonempty subsequences. Find how many of them are good.

As this number can be very large, output it modulo $10^9 + 7$.

An array $c$ is a subsequence of an array $d$ if $c$ can be obtained from $d$ by deletion of several (possibly, zero or all) elements.

Lee 最近一直睡不着，因为他总是做噩梦。在其中一个噩梦里（梦到了一场不平衡的全球赛），他决定奋起反击，并提出了下面这道题（你需要解决它），以期让比赛恢复平衡，从而让他摆脱噩梦。

一个非空数组 $b_1, b_2, \ldots, b_m$ 被称为好数组，当且仅当存在 $m$ 个整数序列，满足以下性质：

• 第 $i$ 个序列由 $b_i$ 个连续整数构成（例如，若 $b_i = 3$，则第 $i$ 个序列可以是 $(-1, 0, 1)$ 或 $(-5, -4, -3)$，但不能是 $(0, -1, 1)$ 或 $(1, 2, 3, 4)$）；
• 设第 $i$ 个序列中所有整数之和为 $sum_i$，我们要求 $sum_1 + sum_2 + \ldots + sum_m = 0$。

现给定一个数组 $a_1, a_2, \ldots, a_n$。它共有 $2^n - 1$ 个非空子序列。请计算其中有多少个是好数组。

由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

数组 $c$ 是数组 $d$ 的一个子序列，当且仅当 $c$ 可通过从 $d$ 中删除若干（可能为零个或全部）元素得到。

The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the size of array $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — elements of the array.

第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）——数组 $a$ 的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）——数组的元素。

Print a single integer — the number of nonempty good subsequences of $a$, modulo $10^9 + 7$.

输出一个整数——数组 $a$ 的非空“好”子序列的个数，对 $10^9 + 7$ 取模。

For the first test, two examples of good subsequences are $[2, 7]$ and $[2, 2, 4, 7]$:

For $b = [2, 7]$ we can use $(-3, -4)$ as the first sequence and $(-2, -1, \ldots, 4)$ as the second. Note that subsequence $[2, 7]$ appears twice in $[2, 2, 4, 7]$, so we have to count it twice.

Green circles denote $(-3, -4)$ and orange squares denote $(-2, -1, \ldots, 4)$.

For $b = [2, 2, 4, 7]$ the following sequences would satisfy the properties: $(-1, 0)$, $(-3, -2)$, $(0, 1, 2, 3)$ and $(-3, -2, \ldots, 3)$

对于第一个测试用例，两个优秀的子序列示例是 $[2, 7]$ 和 $[2, 2, 4, 7]$：

对于 $b = [2, 7]$，我们可以取 $(-3, -4)$ 作为第一个序列，取 $(-2, -1, \ldots, 4)$ 作为第二个序列。注意子序列 $[2, 7]$ 在 $[2, 2, 4, 7]$ 中出现了两次，因此需将其计数两次。

绿色圆圈表示 $(-3, -4)$，橙色方块表示 $(-2, -1, \ldots, 4)$。

对于 $b = [2, 2, 4, 7]$，以下序列满足题目要求：$(-1, 0)$、$(-3, -2)$、$(0, 1, 2, 3)$ 和 $(-3, -2, \ldots, 3)$。