Carol and Skrulls

All submissions for this problem are available.
For Turbo C++ Users : Read the following document before attempting the question :
Switching from Turbo to GNU
Problem description.
The Skrulls are attacking our planet! The only way to stop them is to break into their weapons system and disable it. The password to disable the system is written on the machinery itself (in an encrypted form, obviously). Fortunately enough, you (Carol) know how to decrypt it:
You are given a list of 'N' integers. You need to select some elements from this list so that the product of the chosen numbers is biggest possible. At least 1 element has to be selected. Let this be 'X'. Now since 'X' may be too big, we want the remainder of X when it is divided by 1000000007 (ans % 1000000007).
Note about ‘modulo’:
 The modulus operator (%) gives the remainder of division of 2 numbers.
 a % b = the remainder of division with a as ‘dividend’ and b as ‘divisor’.
 For eg. 5%3 = 2, since on dividing 5 by 3, we get 2 as remainder.
 Most languages support the % operator as the modulus operator. (to find modulus of x over y, just do z = x%y)
 Since we can’t really calculate the whole product and then take modulo, we take modulo on each step so as to keep the intermediate answer small by exploiting this property (a*b) % m = ((a%m)*(b%m))%m.
 To check overflow, you should use long data types instead of int data types (wherever reqd. and available).
 If x<0 , x%m = (x+m)%m
Input
First line contains 'T', the number of test cases. Each test case consists of two lines. The first line contains 'N', the number of elements in the original list. The next line contains 'N' elements of that list.
Output
For each test case, print the required answer on a new line MODULO 1000000007.
Constraints
 1 ≤ T ≤ 30
 1 ≤ N ≤ 10^{6}
 Subtask 1 (30 points):
 0 ≤ A[i] ≤
10^{6}
 0 ≤ A[i] ≤
 Subtask 2 ( 30 points):
 10^{6} ≤ A[i] ≤
10^{6} ; A[i]!=0
 10^{6} ≤ A[i] ≤
 Subtask 3 (40 points):
 10^{6} ≤ A[i] ≤
10^{6}
 10^{6} ≤ A[i] ≤
Example
Input: 1 4 9 11 771 23 Output: 1755567
Explanation
We select all 4 numbers to yield the maximum product.
Author:  proconjr2015 
Tags  proconjr2015 
Date Added:  10072015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions