FoxSeq

All submissions for this problem are available.
Fox Ciel likes sequences of integers. She especially likes sequences which she considers to be beautiful. A sequence (A[0], A[1], ..., A[N1]), N >= 1, is beautiful if and only if it satisfies the following conditions:
Each element of the sequence is an integer between 0 and 40, inclusive.
Each element of the sequence is less than or equal to the arithmetic mean of the previous elements. That is, for each i, 1 <= i < N, we have A[i] <= (A[0] + A[1] + ... + A[i1]) / i.
There are no three consecutive elements in the sequence that follow in strictly decreasing order. In other words, there must be no index i, 0 <= i < N2, such that A[i] > A[i+1] > A[i+2].
You are given a int[] seq that describes some sequences. Each element in seq is between 1 and 40, inclusive. You can change each occurrence of 1 in seq into an arbitrary integer between 0 and 40, inclusive. Different occurrences can be changed into different integers.
Return the number of different beautiful sequences that can be obtained in this way, modulo 1,000,000,007.
Constraints
1. Two sequences of the same length are different if there is at least one position at which their elements are different.
2. Each element of seq will be between 1 and 40, inclusive.
3. Seq will contain between 1 and 40 elements, inclusive.
Input
The first line contains the size of the array 'n', followed by a line which contains n space separated integers, each containing one element of the array.
Output
Print a single line of output giving the number of different beautiful sequences modulo 1000000007.
Example
Input: 2 3 1 Output: 4Input: 3 5 3 1 Output: 2
Explanation
In the first test case, all possible combinations are as follows : {3,0},{3,1}, {3,2}, {3,3} .
Author:  prog_iitmandi 
Tags  prog_iitmandi 
Date Added:  25102012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, PIKE, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, JS, ERL, PERL6, CLOJ, FS 
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. 