Math Hatter

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
The education system of Wonderland was designed by the great psychologist Math Hatter. In Wonderland there are n kids attending school. For simplicity they are numbered from 1 to n. Math Hatter noticed that all of them are very smart, so he measured their Intellectual Quotient (IQ), it turned out that no two students had the same IQ and that all IQs were integers in the range from 1 to n.
In the Math Hatter's education system, one kid can be the teacher of many other kids, and also be the pupil of many others.
Let j be the smallest integer greater than i such that the IQ of kid j is greater than the IQ of kid i, the pupils of kid i are all the kids numbered from i + 1 to j  1. If no such j exist we consider j to be equal to n + 1, note that kid number i will not have any pupils when j = i + 1 or when i = n.
Math hatter doesn't remember the IQ of each kid, however he remembers their number of pupils. Using this information Math Hatter is trying to recover the IQ of each kid. Help him calculating the number of IQ assignations that he can find. As the answer could be large, output it modulo 10^{9} + 7.
Input
The first line of the input contains one integer T the number of test cases. The description of T test cases follows.
Each test case consists of two lines.
The first line contains one integer n the number of kids, the second line contains n space separated integers c_{i} denoting the number of pupils of kid i.
Output
For each test case, output the answer to the problem modulo 10^{9}+7.
Constraints
 1 ≤ n ≤ 10^{5}, the sum of n over all test cases is at most 10^{6}
 0 ≤ c_{i} < n
Example
Input: 2 4 0 2 1 0 4 0 2 1 1 Output: 3 0
Explanation
In the first example, the possible students IQs are the following:
 [1, 4, 3, 2]
 [2, 4, 3, 1]
 [3, 4, 2, 1]
In the second example, there are no possible assignments because the last student can't have one pupil.
Author:  alei 
Tester:  kingofnumbers 
Editorial  http://discuss.codechef.com/problems/MADHAT 
Tags  alei, combinatorics, cook73, easymedium, maths 
Date Added:  21072016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions