Recurrence 

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

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(3, 3, 2, 1) = F(3, 3, 2, 1) + F(4, 2, 2, 1) + F(4, 3, 1, 1) + F(4, 3, 2, 0)
F(1, 1, 0, 0) = F(0, 1, 0, 0) + F(1, 0, 0, 0) + F(1, 1, - 1, 0) + F(1, 1, 0, - 1) = 2
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 

Input starts with an integer T (T$ \le$50), denoting 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.

Output 

For each test case 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(P1, P2, P3,..., Pn) mod 1, 000, 000, 009.

Sample Input 

8
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

Sample Output 

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