Recurrence |
Consider a tuple P_{1}, P_{2}, P_{3},..., P_{n}. 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(P_{1}, P_{2}, P_{3},..., 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 (T50), 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.
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
Case 1: 100100 Case 2: 398009117 Case 3: 9 Case 4: 25025 Case 5: 923714728 Case 6: 311516464 Case 7: 1430 Case 8: 315