D. 子序列zero

题目描述

给定一个长度为$n$的序列，现在想选一个连续非空的子序列，并给每个元素前面加上正负号，使得这个子序列的和恰好为0，问有多少种方案。注意同一个子序列，如果有多种添加符号的方法算不同的方案。答案对998244353取模

输入格式

第一行输入一个整数$n$

接下来一行输入$n$个整数$a_1, a_2, a_3, \cdots a_n$

输出格式

输出一个整数表示答案对998244353取模的结果

输入样例1

4
1 1 1 1

输出样例1

12

数据范围：

对于30%的数据，$n \leq 18$

对于60%的数据，$n \leq 100$

对于100%的数据，$n \leq 1000, 1 \leq a_i \leq 10$