时间限制:1000ms  空间限制:256MB

题目描述

  飞翔的祖母一直和飞翔住在一起。老太太非常喜欢自己的孙子，在飞翔小时候经常给他讲故事。有的故事，会让飞翔非常开心；有的故事，会让飞翔非常悲伤。为了平复飞翔的心情，祖母讲完一个开心的故事，就会接着讲一个悲伤的故事~~ ；如果先讲了一个悲伤的故事，后面就会讲一个开心的故事。 总之，开心的故事和悲伤的故事数量要一致，心情才能平复。 祖母一共有 $n$ 个故事。现在按照顺序给出 $n$ 个故事的属性（1 表示开心，-1 表示悲伤），请你统计有多少种方案，是可以让飞翔保持心情平静的。故事的选取，必须是连续的。结果请对 2019 求余。

输入格式

共 2 行：第一行为 $n$ ，表示故事的个数；第二行为 $n$ 个用空格隔开的 1 和 -1 序列，表示故事是开心的，还是悲伤的。

输出格式

一行，一个整数，方案数对 2019 求余的结果。

样例

输入#1

9 
-1 1 -1 -1 -1 1 1 -1 -1

输出#1

8

解释#1

（非官方解释）选择以下 8 种方案都可以使得飞翔平静：

1 ~ 2：-1,1

2 ~ 3:1,-1

2 ~ 7:1,-1,-1,-1,1,1

4 ~ 7:-1,-1,1,1

5 ~ 6:-1,1

5 ~ 8:-1,1,1,-1

6 ~ 9:1,1,-1,-1

7 ~ 8:1,-1

数据范围/约定

40% 的数据 $1<=n<=1000$

100% 的数据 $1<=n<=1000000$

备注

题中“为了平复飞翔的心情，祖母讲完一个开心的故事，就会接着讲一个悲伤的故事；如果先讲了一个悲伤的故事，后面就会讲一个开心的故事。” 这句话可以忽略，不要读它，会误导你。实际题目要求是： 只要一段连续的故事中，悲伤的故事和开心的故事数量相等，就满足要求 。