题目描述

给定 $n$ 个数字 $a_1,a_2,\dots,a_n$，可以将它分割成任意多段，每一段可以有任意多个数字，唯一的要求是每段的数字之和都要大于或等于 $0$。

请问有多少种分段方法？由于答案可能很大，输出方案数模 $1,000,000,007$ 的余数。

例如当数列为 $1,-2,3,-1$ 时，只有两种合适的分割方案：

• $(1, -2,3,-1)$
• $(1), (-2,3,-1)$

输入格式

• 第一行：单个整数表示 $n$
• 第二行：$n$ 个整数表示 $a_1,a_2,\dots,a_n$

输出格式

单个整数：表示方案数模 $1,000,000,007$ 的余数。

4
1 -2 3 -1

2

样例解释 1

有两种分法 (1,-2,3,-1) 和 (1)(-2,3,-1)

数据范围

• 对于 $30\%$ 的数据，$n\leq 100$
• 对于 $60\%$ 的数据，$n\leq 5000$
• 对于 $100\%$ 的数据，$1\leq n\leq 200,000$
• $-1,000,000\leq a_i\leq 1,000,000$