飞翔的祖母一直和飞翔住在一起。老太太非常喜欢自己的孙子，在飞翔小时候经常给他讲故事。有的故事，会让飞翔非常开心；有的故事，会让飞翔非常悲伤。~~为了平复飞翔的心情，祖母讲完一个开心的故事，就会接着讲一个悲伤的故事~~ ；如果先讲了一个悲伤的故事，后面就会讲一个开心的故事。 总之，开心的故事和悲伤的故事数量要一致，心情才能平复。 祖母一共有 nn 个故事。现在按照顺序给出 nn 个故事的属性（1 表示开心，-1 表示悲伤），请你统计有多少种方案，是可以让飞翔保持心情平静的。故事的选取，必须是连续的。结果请对 2019 求余。
选择以下 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<=10001<=n<=1000
100% 的数据 1<=n<=10000001<=n<=1000000
备注
题中“为了平复飞翔的心情，祖母讲完一个开心的故事，就会接着讲一个悲伤的故事；如果先讲了一个悲伤的故事，后面就会讲一个开心的故事。” 这句话可以忽略，不要读他，会误导你。实际题目要求是： 只要一段连续的故事中，悲伤的故事和开心的故事数量相等，就满足要求 。