C. Painting Stones
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Pedro has $$$n$$$ stones arranged in a row and wants to paint them with $$$c$$$ different colors in such a way that no two consecutive stones are of the same color.

He has already painted some of the stones and now he wonders how many ways he can paint the remaining stones to achieve his goal.

Input

The input starts with a line containing an integer $$$t$$$ indicating the number of cases.

Each case starts with two integers $$$n$$$ and $$$c$$$. The second line of each case contains $$$n$$$ integers $$$x_i$$$ with $$$0 \leq x_i \leq c$$$, where each positive integer represents a color and $$$0$$$ indicates that the stone has not been painted.

The answer can be very large, so write the result modulo $$$10^9+7$$$.

Output

For each case, write a line with the result modulo $$$10^9+7$$$.

Scoring

$$$1 \leq t \leq 100$$$

11 Points: $$$1 \leq n,c \leq 10$$$, $$$c^n \leq 10^4$$$

20 Points: $$$1 \leq n,c \leq 100$$$

20 Points: $$$1 \leq n,c \leq 1000$$$

32 Points: $$$1 \leq n,c \leq 10^4$$$

17 Points: $$$1 \leq n \leq 10^4$$$, $$$1 \leq c \leq 10^9$$$

Example
Input
4
3 4
1 0 1
3 4
2 0 3
5 6
0 0 1 0 2
4 3
0 1 1 2
Output
3
2
100
0