The memory of Bob’s computer contains two interesting things: an array of integers and a virus.
Each midnight the virus becomes active. It takes each array in memory and replaces it with a bunch of new arrays: one for each contiguous subarray of the original array.
For example, if today the memory contains a single array (1,2,1,3), tomorrow it will contain the following arrays: (1), (2), (1), (3), (1,2), (2,1), (1,3), (1,2,1), (2,1,3), and (1,2,1,3).
Problem specification
You are given the length N of Bob’s original array, its contents and the number of days D.
Compute the sum of all elements of all arrays that will be in the memory of Bob’s computer after D days. As this number can be huge, it is sufficient to compute the remainder it gives when divided by 109 + 9.
Assume that the memory of Bob’s computer is sufficiently large to accommodate all the arrays.
Input specification
The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of two lines. The first line contains the two integers N and D. The second line contains N small non-negative integers: the contents of the original array.
In the easy data set you may assume that the total number of elements in all arrays after D days will be at most 10000000.
In the hard data set you may assume that N ≤ 50 and D ≤ 1000.
Output specification
For each test case output a single line with a single integer: the sum of all elements in all arrays after D days, modulo 1,000,000,009.
Example
The first test case corresponds to the example in the problem statement.
An additional challenge (just for fun)
The problem is solvable even if the constraints were, say, N,D ≤ 100000. Can you see a solution that would be efficient enough to solve such a huge test case?
If you think you know such a solution, you can test it on the following input: N = D = 100000, array = (1,2,3,…,99999,100000). The correct output is 92629705.