9731번 - Recurrence 다국어

Consider a tuple P1,P2,P3,…,Pn. Now consider the following recurrence function.

\( F(P_1,P_2,P_3,...,P_n)= \begin{cases} 0  & \text{if any of the P_i is negative or the tuple P is not sorted in non-increasing order} \\ F(P_1-1,P_2,P_3,...,P_n)+F(P_1,P_2-1,P_3,...,P_n)+ \\ F(P_1,P_2,P_3-1,...,P_n)+...+F(P_1,P_2,P_3,...,P_n-1)   & \text{otherwise} \end{cases} \)

F(0,0,0….,0) = 1.

For example, if n is 4 then the value
F(4,3,2,-1) is 0 because the last parameter is negative.
F(4,3,2,5) is 0 because the tuple is not sorted from the largest to smallest.
F(4,3,2,1) = F(3,3,2,1)+F(4,2,2,1)+F(4,3,1,1)+F(4,3,2,0)
Given the tuple P, your task is to calculate the value of F(P₁,P₂,P₃,…,P_n).
The result can be very big so output the result mod 1,000,000,009 (this is
a prime number). 

Input starts with an integer T, the number of test cases.
Each test case consists of two lines. First line contains n. Second line contains n integers separated by a single space. These are the tuple P. n is between 1 and 1000 inclusive. Each of the numbers in tuple P is between 1 and 1000 inclusive. P will be sorted in non-increasing order.

For each test case, the output contains a line in the format Case #x: R, where x is the case number (starting from 1) and R is the value of F(P_1,O_2,P_3,…,P_n) mod 1,000,000,009.