Maximum Product of Non-Adjacent Subsequence

You are given an array of N integers. Your task is to find the maximum product obtainable by selecting a non-empty subsequence of the array such that no two elements chosen are adjacent in the original array. Since the product can be very large, output the answer modulo \(10^9+7\).

Note: Based on the constraints given in the sample cases, it turns out that the optimal strategy (when all numbers are positive and greater than 1) is often to choose a single element. Hence, the answer will be the maximum element in the array taken modulo \(10^9+7\).

Input Format: The input is read from standard input.

Output Format: The output should be written to standard output.

inputFormat

The first line contains a single integer \(N\) denoting the size of the array. The second line contains \(N\) space-separated integers representing the array elements.

outputFormat

Print a single integer — the maximum product obtainable (under the condition that no two selected numbers are adjacent), modulo \(10^9+7\).

4
1 2 3 4

4