Consider a tuple P1, P2, P3, . . . , Pn. Now consider the following recurrence function. • F(P1,P2,P3,...,Pn) = 0 if any of the Pi is negative or the tuple P is not sorted in non-increasing order. • F(P1,P2,P3,...,Pn) = 1 if all of the Pis is zero. • F(P1,P2,P3,...,Pn) = F(P1 − 1,P2,P3,...,Pn) + F(P1,P2 − 1,P3,...,Pn) + F(P1,P2,P3 − 1,...,Pn)+F(P1,P2,P3,...,Pn −1) otherwise. 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 mod1, 000, 000, 009 (this is a prime number). Input Input starts with an integer T (T ≤ 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 Foreachtestcaseoutputcontainsalineintheformat‘Casex: R’wherexisthecasenumber(starting from 1) and R is the value of F(P1,P2,P3,...,Pn) mod 1,000,000,009. Sample Input 8 3 754 6 775321 2 42 3 744 4 8755 5 77655 2 87 3 631
2/2 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