← 返回题目列表

Codeforces · 1610/D

D. 不完全是李

中文机器翻译题面 查看原题

李最近睡不着,因为他做了噩梦。在他的一个噩梦中(关于不平衡的全球回合),他决定反击并提出一个下面的问题(你应该解决)来平衡回合,希望能让他摆脱噩梦。

如果存在满足以下属性的 $$$m$$$ 整数序列,则非空数组 $$$b_1, b_2, \ldots, b_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$$$ 获得。

输入

第一行包含一个整数 $$$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$$$) — 数组的元素。

输出

打印单个整数 - $$$a$$$ 的非空好子序列的数量,以 $$$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

注意

对于第一个测试,好的子序列的两个示例是 $$$[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)$$$