Sequence Artisan

Interview

Time limit1sMemory limit256 MB

Summary

Find the largest product of any contiguous block in an array with values from -2 to 2, then report it modulo 1000000007.

Level: Medium5 of 10
Topics: Greedy, Dynamic programming, Math
Solved: No attempts yet

Problem

Seunghyun builds sequences $a_1, a_2, \dots, a_N$ of length $N$ for customers who need one. He is early in his career, so he can only build sequences whose elements are integers between $-2$ and $2$ , and few customers come to him.

Jihak ordered a sequence from him. From the finished sequence Jihak picks one contiguous block $a_i, a_{i+1}, \dots, a_{j-1}, a_j$ ( $1 \le i \le j \le N$ ) and wants the product of its elements, $a_i \times a_{i+1} \times \dots \times a_{j-1} \times a_j$ , to be as large as possible. If $i = j$ , the product is $a_i$ .

Given the sequence Seunghyun built, find the largest product Jihak can obtain.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 100000$ ). The $T$ test cases follow.

The first line of each test case contains the length of the sequence $N$ ( $2 \le N \le 100000$ ). The second line contains the elements $a_1, a_2, \dots, a_N$ ( $-2 \le a_i \le 2$ ), separated by spaces.

The sum of $N$ over all test cases does not exceed $300000$ .

Output

For each test case, print the largest product modulo $1{,}000{,}000{,}007$ ( $= 10^9 + 7$ ) on its own line.

Compare the true products when choosing the largest one, then reduce only that chosen value modulo $10^9 + 7$ .

Examples4

Example 1

Input

3
5
1 2 -1 2 1
5
1 2 -1 2 -1
2
2 -1

Expected output

2
4
2

Example 2

Input

4
5
0 0 0 0 0
3
-1 0 -2
2
0 2
6
2 0 -2 -2 0 1

Expected output

Example 3

Input

Expected output

Example 4

Input

3
5
-1 -1 -1 -1 -1
4
-2 -2 -2 -2
7
-2 1 -2 0 -2 -2 2

Expected output

1
16
8