Random Rudreshwar

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Problem description
Rudreshwar likes random numbers and random arrays. Today Rudreshwar started playing with a couple of Arrays A and B, each of size N.
Initially A is filled with zeros. Rudreshwar filled B with random numbers.
Rudreshwar visits each index i (1 <= i <= N) in random order. When at i, he selects another random index j such that j is greater or equal to i. He then increments A[i], A[i+1], A[i+2] ... A[j] by 1.
Finally if for any index i, A[i] is greater than B[i], he then throws away that array A
For a given B, calculate the number of different arrays A, that Rudreshwar can end up with. Two arrays are called different if there exists an index where the arrays have different values
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. First line of each test case contains an integer N. Second line contains N space separated integers representing the array B
Output
For each test case, output a single line containing the required answer modulo 1000000007.
Constraints
 1 ≤ T ≤ 100
 1 ≤ N ≤ 1000
 1 ≤ B[i] ≤ N
Example
Input: 2 2 2 2 3 1 1 1 Output: 2 1
Explanation
Test case 1
{1, 1} and {1, 2} are valid.
Test case 2
{1, 1, 1} is the only possible final array A.
Author:  anudeep2011 
Tester:  xiaodao 
Editorial  http://discuss.codechef.com/problems/ANURRZ 
Tags  anudeep2011, cook54, dynamicprogramming, medium 
Date Added:  6012015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 