시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 862 98 83 16.468%

문제

승현이는 수열을 찾는 사람들을 위해 길이가 N 인 수열 a1, a2, ··· , aN을 만드는 일을 하고 있다. 승현이는 경력이 짧아서 각 원소가 -2 이상 2 이하의 정수인 수열만 만들 수 있고, 그래서인지 수열을 찾는 고객이 많지 않아 승현이는 생활고에 시달리고 있다.

이를 지켜보던 지학이는 안타까운 마음에 승현이에게 수열을 하나 만들어달라고 의뢰했고, 승현이는 기쁜 마음으로 수열을 만들어 주었다. 지학이는 이 수열에서 임의의 연속하는 부분 ai, ai+1, ··· , aj−1, aj (1 ≤ i ≤ j ≤ N)를 선택하여, 선택한 부분의 원소들의 곱 ai × ai+1 × · · · × aj−1 × aj 가 최대가 되게 하려고 한다. (단 i = j 이면 곱의 결과를 ai 로 정의한다.)

승현이가 만든 수열이 주어질 때, 지학이가 만들 수 있는 곱의 최댓값을 구하는 프로그램을 작성하라.

입력

첫 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 100,000)가 입력된다. 이후 T 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 승현이가 만든 수열의 길이 N (2 ≤ N ≤ 100,000)이 주어지고, 두 번째 줄에는 승현이가 만든 수열의 각 원소 a1, a2, ··· , aN (−2 ≤ ai ≤ 2)이 공백을 사이에 두고 주어진다.

모든 테스트 케이스에 대한 N 의 총합이 300,000을 넘지 않음이 보장된다.

출력

각 테스트 케이스에 대해, 지학이가 만들 수 있는 곱의 최댓값을 1,000,000,007 (= 109+7)으로 나눈 나머지를 한 줄에 하나씩 출력한다.

예제 입력

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

예제 출력

2
4
2

힌트