Sereja and Data Structures

All submissions for this problem are available.
Sereja is a little student from the University of Kyiv. He studies computer science. He is rather experienced programmer and he knows a lot of advanced algorithms. The only thing he likes more than advanced algorithms is segment tree data structure.
Every evening he goes to the loveliest place in Kyiv  The Chef's cafe. Chef is also interested in computer science, so they often discuss different problems. Last evening Sereja told Chef following problem: given an array A_{1}, A_{2}, ..., A_{N} of N integers. The task is to find the product of ranges of the segments [i, j] over 1 ≤ i < j ≤ N, where the range of the segment [i, j] means max(A_{i}, A_{i+1}, ..., A_{j})  min(A_{i}, A_{i+1}, ..., A_{j}).
Both Sereja and Chef couldn't find any efficient algorithm for this problem with segment tree. They gave up thinking of it, and Chef said we may calculate this value only for a random array, that means all elements of the array are generated uniformly and independently at random. Sereja were surprised to hear that, and he wanted to know about details. However Chef is very busy at the moment, so he asked you to solve this problem for a random array.
Input
The first line contains a single integer N, then N integers A_{1}, A_{2}, ..., A_{N} follow on the second line.
Output
Output a single line containing the required product modulo 1000000007 (10^{9}+7), since the answer can be very large.
Constraints
2 ≤ N ≤ 100000 (10^{5})
0 ≤ A_{i} < 1000000007 (10^{9}+7)
All test cases, except Example, are created by the method described in Test Case Generation.
Example
Input 1: 3 1 2 4 Output 1: 6 Input 2: 5 5 5 5 5 5 Output 2: 0
Explanation
In Input 1, we should consider 3 segments [i, j] = [1, 2], [2, 3], [1, 3].
The range of segment [1, 2] is max(1,2)  min(1,2) = 1.
The range of segment [2, 3] is max(2,4)  min(2,4) = 2.
The range of segment [1, 3] is max(1,2,4)  min(1,2,4) = 3.
Therefore, we obtain the answer 1 * 2 * 3 = 6, and you should output 6 mod 1000000007 = 6.
In Input 2, we should consider 10 segments, but all ranges of such segments are 0. And, of course, the answer is 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 = 0.
Note that Example is created by manually, so these arrays are not random arrays. It is quite unlikely that the official test cases contain an array with equal elements such as Input 2.
Test Case Generation
There are 15 official test files.For every test file, A_{i} are chosen from 0 to 1000000006 (10^{9}+6) uniformly and independently at random.
The first 5 test files: N is chosen from 2 to 100 uniformly at random.
The next 5 test files: N is chosen from 2 to 100000 (10^{5}) uniformly at random.
The last 5 test files: N = 100000 (10^{5})
Author:  rubanenko 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/SEREJA 
Tags  Rubanenko, dec12, medium, simplemath 
Date Added:  2082012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions