Not Quite Lee

题意翻译

对于一个长度为为 $m$ 的序列 $b$，我们称其为「好的」，当且仅当其满足以下条件： - 我们可以根据该序列构造出 $m$ 个序列，其中第 $i$ 个序列长度为 $b_i$，并且由 $b_i$ 个连续整数组成。（连续定义为后一个数比前一个数大 $1$，例如序列 $[-1,0,1]$ 即由 $3$ 个连续整数组成） - 令 $sum_i$ 为其中第 $i$ 个序列所有元素的和，那么需要满足 $\sum_{i=1}^m sum_i$ 等于 $0$。 给定长度为 $n$ 的序列 $a$，蓝希望你能求出其好的非空子序列的个数模 $10^9+7$ 的值。 定义序列 $c$ 为序列 $a$ 的子序列，当且仅当其可以由 $a$ 删除若干元素得到。（特别的，$a$ 本身也为 $a$ 的子序列） 本题数据保证：$1 \leq n \leq 2\times10^5$，$1 \leq a_i \leq 10^9$。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

4
2 2 4 7

输出样例 #1

10

输入样例 #2

10
12391240 103904 1000000000 4142834 12039 142035823 1032840 49932183 230194823 984293123

输出样例 #2

996

说明

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) $