题目背景

本题是 1-1 的较难版本，较易版本为 1-1 A。

题目描述

给出一个序列 $a$，$\forall i\in [1,n],a_i\in \{1,-1\}$。

询问有多少个将 $a$ 重排后的序列使得该序列的最大子段和最小化。

称两个序列不同，当且仅当这两个序列有任意一个位置上的数不同。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数表示 $a$。

输出格式

一个整数表示答案。答案对 $998244353$ 取模。

4
1 -1 1 -1

3

5
1 1 1 -1 1

3

10
1 1 1 1 1 1 1 -1 -1 -1

40

提示

最大子段和的定义：序列中一段区间的和的最大值。即 $\max_{1\le l\le r\le n} \sum_{i=l}^r a_i$。

数据规模

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\le n\le 10^4$，$a_i\in \{1,-1\}$。