Problem Description
Rar the Cat has a row of N fish on his dinner table, numbered 0 to N - 1 from left to right, and the ith fish has a tag with the integer Ai hung onto it.
Rar can pick any non-empty consecutive segment of fish to eat for lunch, but he decides that the satisfaction of the meal would be equivalent to the product of the tag numbers of all the fish he ate.
Help Rar determine the maximum satisfaction he can get, modulo 109 + 7.
Input
The first line of input will contain one integer, N.
The next line of input will contain N integers, with the ith integer being Ai.
Output
The output should contain one integer, the maximum satisfaction, modulo 109 + 7.
Limits
Subtask 1 (8%): 1 ≤ N ≤ 2 000, |Ai| ≤ 109. The answer would fit into a signed 64-bit integer.
Subtask 2 (17%): 1 ≤ N ≤ 2 000, |Ai| ≤ 109.
Subtask 3 (13%): 1 ≤ N ≤ 100 000, 0 ≤ Ai ≤ 109.
Subtask 4 (20%): 1 ≤ N ≤ 100 000, |Ai| ≤ 1.
Subtask 5 (19%): 1 ≤ N ≤ 100 000, |Ai| ≤ 109.
Subtask 6 (23%): 1 ≤ N ≤ 1 000 000, |Ai| ≤ 109.
Subtask 7 (0%): Sample Testcases
Sample Testcase 1
Input
5
-4 -2 -2 3 6
Output
72