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

( 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.

예제 입력

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

예제 출력

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