Description

There are $n$ buildings on the side of Bytestreet, standing sequentially one next to the other, labeled by $1,2,\dots,n$ from east to west. The city planning investigation is going to plant some trees in front of these buildings. A tree planting plan is beautiful if and only if it satisfies all the conditions below:

• At least one tree is planted.
• A tree can only be planted in front of a building, and two trees can not be planted in front of the same building. In other words, let $c_i$ denote the number of trees planted in front of the $i$-th building, $c_i\in\{0,1\}$ holds for all $i=1,2,\dots,n$.
• For every possible value of $i$ ($1\leq i<n$), $c_i$ and $c_{i+1}$ shouldn't both be $1$.
• For every possible value of $i$ ($1\leq i\leq n-k$), $c_i$ and $c_{i+k}$ shouldn't both be $1$. The beautifulness of a plan is defined as:[\prod_{1\leq i\leq n,c_i=1}w_i]You need to find the sum of beautifulness among all the beautiful plans. Two plans are considered different if there exists any $i$ ($1\leq i\leq n$) such that they differ in $c_i$.

Format

Input

The first line contains a single integer $T$ ($1 \leq T \leq 200$), the number of test cases. For each test case:

The first line contains two integers $n$ and $k$ ($2 \leq k<n \leq 300$), denoting the number of buildings and the value of $k$.

The second line contains $n$ integers $w_1,w_2,\dots,w_n$ ($1\leq w_i\leq 10^9$).

It is guaranteed that there will be at most $10$ test cases such that $n>100$.

Output

For each test case, output a single line containing an integer, denoting the sum of beautifulness among all the beautiful plans. Note that the answer may be extremely large, so please print it modulo $10^9+7$ instead.

Samples

2
5 3
1 1 1 1 1
5 4
1 2 3 4 5

10
55