Maximum Subarray Product Modulo

Given an integer \(n\) and an array of \(n\) integers, find the maximum possible product of any non-empty contiguous subarray. The subarray product is defined as the product of all its elements.

Since the result can be very large or negative, output the result modulo \(10^9+7\). Note that for a negative result, the modulo operation should yield a non-negative integer.

inputFormat

The first line contains a single integer \(n\), the number of elements in the array.

The second line contains \(n\) space-separated integers, representing the elements of the array.

outputFormat

Output a single integer, the maximum product of any contiguous subarray modulo \(10^9+7\).

4
-2 0 -1 4

4