시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB1812650.000%

## 문제

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(P1,P2,P3,…,Pn).
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.

## 예제 입력 1

10
3
7 5 4
6
7 7 5 3 2 1
2
4 2
3
7 4 4
4
8 7 5 5
5
7 7 6 5 5
2
8 7
3
6 3 1
4
8 7 4 4
3
6 3 2


## 예제 출력 1

Case #1: 100100
Case #2: 398009117
Case #3: 9
Case #4: 25025
Case #5: 923714728
Case #6: 311516464
Case #7: 1430
Case #8: 315
Case #9: 41100051
Case #10: 990