[ARC180] C - Subsequence and Prefix Sum

C - Subsequence and Prefix Sum

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 600 分

题面

给定长度为 的整数序列 。

你将执行以下操作一次：

• 选择 的一个非空子序列（不一定连续），并用它的累积和替换它。更详细地说，首先选择一个索引序列 ，其中 。序列的长度 () 可以任意选择。然后，对于每个 ()，用 替换 的值。所有选定的索引都同时进行替换。

找出操作后可能的序列 的数量，对 取模后的结果。

限制条件

• 所有输入值都是整数。

---

输入

输入来自标准输入，格式如下：

输出

输出答案。

---

输入样例 1

3
1 1 2

输出样例 1

4

操作后可能的序列 如下：

• : 可以通过 和 实现。
• : 可以通过 和 实现。
• : 可以通过 和 实现。
• : 可以通过 和 实现。

---

输入样例 2

4
1 -1 1 -1

输出样例 2

8

---

输入样例 3

5
0 0 0 0 0

输出样例 3

1

---

输入样例 4

40
2 -2 1 3 -3 -1 -2 -3 0 -1 -2 0 -3 0 0 2 0 -1 2 -2 -2 -1 3 -2 -2 -2 2 3 2 -3 0 -2 2 1 3 0 -1 0 -2 -3

输出样例 4

420429545