수열의 장인

승현이는 수열을 찾는 사람들을 위해 길이가 $N$인 수열 $a_1, a_2, \dots, a_N$을 만드는 일을 한다. 경력이 짧아서 각 원소가 $-2$ 이상 $2$ 이하인 정수 수열만 만들 수 있고, 그래서 찾아오는 고객이 많지 않다.

이를 지켜보던 지학이가 승현이에게 수열을 하나 의뢰했다. 지학이는 완성된 수열에서 연속한 구간 $a_i, a_{i+1}, \dots, a_{j-1}, a_j$ ($1 \le i \le j \le N$)를 하나 골라, 고른 구간의 원소를 모두 곱한 값 $a_i \times a_{i+1} \times \dots \times a_{j-1} \times a_j$를 가장 크게 만들려고 한다. $i = j$이면 곱은 $a_i$로 정의한다.

승현이가 만든 수열이 주어질 때, 지학이가 얻을 수 있는 곱의 최댓값을 구하라.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 100000$)가 주어진다. 이후 $T$개의 테스트 케이스가 이어진다.

각 테스트 케이스의 첫 줄에는 수열의 길이 $N$ ($2 \le N \le 100000$)이 주어진다. 둘째 줄에는 수열의 원소 $a_1, a_2, \dots, a_N$ ($-2 \le a_i \le 2$)이 공백을 사이에 두고 주어진다.

모든 테스트 케이스의 $N$의 총합은 $300000$을 넘지 않는다.

각 테스트 케이스마다 곱의 최댓값을 $1{,}000{,}000{,}007$ ($= 10^9 + 7$)로 나눈 나머지를 한 줄에 하나씩 출력한다.

최댓값은 실제 곱한 값끼리 비교해서 고르고, 그렇게 고른 값 하나만 나머지 연산을 적용한다.