Little X is piloting his spaceship to travel through an $n$-dimensional space, where the coordinates of each point in this space can be represented by $n$ real numbers, namely $(x_1, x_2, \dots, x_n)$.

To travel through this space, Little X needs to select $c$ ($c \ge 2$) points in this space as stopovers for the spaceship. These points must satisfy the following three conditions:

1. Every coordinate of each point is a positive integer, and the $i$-th coordinate does not exceed $m_i$.
2. For the $j$-th coordinate ($1 \le j \le n$), the coordinate of the $(i+1)$-th point must be strictly greater than the coordinate of the $i$-th point ($1 \le i < c$).
3. There exists a straight line passing through all selected points. In this $n$-dimensional space, a straight line can be represented by $2n$ real numbers $p_1, p_2, \dots, p_n, v_1, v_2, \dots, v_n$. The line passes through a point $(x_1, x_2, \dots, x_n)$ if and only if there exists a real number $t$ such that for all $i = 1, \dots, n$, $x_i = p_i + t v_i$.

Little X has not yet determined his final plan. Please help him calculate how many different schemes satisfy his requirements. Since the answer may be very large, you only need to output the answer modulo $10\,007$.

Input

The first line of the input contains a positive integer $T$, representing the number of test cases.

Each test case consists of two lines. The first line contains two positive integers $n, c$ ($c \ge 2$), representing the dimension of the space and the number of stopovers to be selected.

The second line contains $n$ positive integers, representing $m_1, m_2, \dots, m_n$ in order.

Output

The output contains $T$ lines, each containing a non-negative integer corresponding to the answer for each test case.

Examples

Input 1

3
2 3
3 4
3 3
3 4 4
4 4
5 9 7 8

Output 1

2
4
846

Note

For the first sample case, there are two feasible schemes: one is selecting $(1,1), (2,2), (3,3)$, and the other is selecting $(1,2), (2,3), (3,4)$.

Input 2

See space/space.in and space/space.ans in the contestant directory.

Output 2

See space/space.in and space/space.ans in the contestant directory.

Constraints