Description

给你N个数字，每个数字不是1就是-1

问多少个连续的数列和为0

Format

Input

第一行为N， ,N小于等于1e6

第二行为N个用空格隔开的1和-1序列。

Output

总方案数MOD 999999的值

Samples

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

8

Hint

例如第1个数字到第2个数字

第2个到第7个数字

第6个到第9个数字

它们的和均为0

一共有8种情况