题目描述

本题题解已发表至 讨论区

Anya今天放假在家一直看《间谍大战》，Forge觉得一直沉迷于动画片会让Anya的智力变得更低，最后可能无法得到星星，无法完成上司布置的任务，导致东西两国战争爆发，生灵涂炭（昏爹经常这样转眼就是一出戏），于是他给女儿Anya出了一个问题，如果Anya回答出来了，就让Anya继续看电视。

题目描述如下：

一个长度为n的数组，要对所有2<=i<=n-1的i进行以下两种操作的一个：
    1.a[i-1]+=a[i],a[i+1]-=a[i]
    2.a[i-1]-=a[i],a[i+1]+=a[i]
求最终数组的种类数，结果很大，请输出模998244353的结果。

注：操作是从左往右顺次操作的，具体参考样例解释。

Anya才4岁，根本写不出这么困难的题，不过她会读心术⌓‿⌓，通过读父亲的心，她一招秒了。作为她的好朋友，她和你分享了这个题目，想让你也做一做，然后教一下她。

输入描述

一个整数n，代表数组长度。

n个整数，代表数组的值.

3<=n<=350,-350<=a[i]<=350

输出描述

一个对998244353取模的整数，代表从左往右依次操作后可以产生的数组种类数

示例 1

输入

4
1 1 1 1

输出

3

说明

[1,1,1,1]-op1->[2,1,0,1]-op1->[2,1,0,1]
[1,1,1,1]-op1->[2,1,0,1]-op2->[2,1,0,1]
[1,1,1,1]-op2->[0,1,2,1]-op1->[0,3,2,-1]
[1,1,1,1]-op2->[0,1,2,1]-op2->[0,-1,2,3]