Sequence Artisan

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.

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$.

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$.