MoonLight的运算问题
题号：NC253617
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

月色哥哥手中有一个数字 x，最初 x=0。

给出一个长度为 n 的序列 a，月色哥哥会从序列的第一个元素 a_1 按顺序看到序列的最后一个元素 a_n。对于序列的第 i 个元素 a_i，月色哥哥可以进行下面的操作之一：

  •  令 x=x\cdot a_i；
  •  令 x=x + a_i。

请求出 x 的最大值，并输出这个最大值除 998244353 的余数。

输入描述:

第一行包含一个整数 T(1\leq T \leq 10^5)，表示测试用例的组数。

对于每组测试用例：

第一行包含一个整数 n(1\leq n\leq 2\cdot 10^5)，表示序列的长度。

第二行包含 n 个整数 a_1\dots a_n(0\leq a_i\leq 10^9)，表示该序列。

保证对于所有的测试用例，n 的总和不超过 2\cdot 10^5。

输出描述:

对于每组测试用例：

仅输出一行，包含一个整数，表示答案。
示例1

输入

复制 
3
2
1 1
1
0
1
998244353

输出

复制 
2
0
0