Maximum Subarray Product Modulo

You are given an array of integers. Your task is to find the maximum product modulo \(10^9+7\) among all contiguous subarrays of the given array.

For a given subarray \(a[i..j]\), the product is defined as \(P = a[i] \times a[i+1] \times \cdots \times a[j]\) and you should compute \(P \mod (10^9+7)\). Output the maximum \(P \mod (10^9+7)\) over all possible contiguous subarrays.

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 array elements.

outputFormat

Output a single integer representing the maximum product modulo \(10^9+7\) among all contiguous subarrays.

4
1 2 3 4

24