시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB111100.000%

## 문제

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

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.

## 입력

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 consists of N non-negative integers that are all less than 100,000: the contents of the original array.

You may assume that N ≤ 100,000 and D ≤ 100,000.

## 출력

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.

## 예제 입력 1

3

4 1
1 2 1 3

1 10
47

2 10
1 2


## 예제 출력 1

34
47
33


## 힌트

You can test it on the following input: N = D = 100000, array = (1,2,3,…,99999,100000). The correct output is 92629705.