Another Contest 9 Problem 2 - Counting Down the Days

View as PDF

Points: 7
Time limit: 1.0s
Memory limit: 256M

Problem type

Nick is learning how to do yoga. Over the course of the next days, he will pick a contiguous nonempty block of days and do yoga during all of them. Each day has a score associated with it. The score of the yoga interval is equal to the product of all the scores of the days when Nick did yoga.

Compute the maximum possible score Nick can get.

Constraints

The sum of over all test cases is at most .

Input Specification

The first line contains a single positive integer, , the number of test cases. test cases follow.

Each test case starts with a line containing a single positive integer . The next line contains space-separated integers, the values representing the scores of the days in order.

Output Specification

Output the answers for the test cases in order. There should be no blank lines in your output.

The answer for the th test case should be on the th line. If is the maximum score that Nick can attain when doing yoga, output modulo 998244353. Note that you are trying to maximize , not modulo 998244353.

Sample Input

2
3
2 -2 2
30
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Sample Output

2
75497471