Santa Claus has gathered ~n~ children sitting in a perfect circle. Each child ~i~ sits between child ~(i-1)~ and child ~(i+1)~, with child ~1~ and child ~n~ also sitting next to each other.

Initially, Santa distributed candies to the children. However, the children have already divided them among themselves in some way, possibly unfairly, and some children may even have none. Watching this, Santa recalls his younger days, when he often shared his candies so generously that he ended up with less or even none. Feeling nostalgic, he decides that every child should have the same number of candies.

To achieve this, Santa may give simple instructions. In each second, he may pick any child who currently has at least ~2~ candies and tell that child to give one candy to each of their two neighboring children. We call an initial distribution of candies fair if there exists a finite sequence of instructions (following the rule above) such that, after performing them, every child has the same number of candies.

However, Santa does not know the number of candies of every child. Some children are already sitting in the circle and truthfully report their number of candies, while the rest are still out playing and have not returned yet, and Santa has no information about their candy counts. He knows that each child has at most ~K~ candies.

Given the reported values for the children already present, Santa wonders: How many possible candies states that is considered fair with the numbers he already knows?

Help Santa compute the number of such fair candies states

Input

The first line contains a positive integer ~T~ (~1 \le T \le 500~) — the number of test cases. Each test case is described as follows:

The first line contains a positive odd integer ~n~ (~3 \le n \le 500~, ~1 \le K \le 10^9~) — the number of children, and the maximum number of candies a child initially has.

The second line contains ~n~ integers ~a_1, a_2, \dots, a_n~ (~-1 \le a_i \le K~), the number of candies that child ~i~ currently has. A value of ~a_i = -1~ means that child ~i~ is still out playing and has not returned to the circle yet, so Santa does not know how many candies they currently hold.

The data guarantees that the total of all values ~n^3~ over all test cases does not exceed ~500^3~.

Output

For each test case, print a single integer — the number of fair initial distributions of candies consistent with the known values, modulo ~10^9 + 7~.

Sample Input 1

2
3 1
1 1 1
3 2
-1 -1 -1

Sample Output 1

1
3

Sample Input 2

2
5 2
2 0 0 2 1
5 2
2 0 0 -1 -1

Sample Output 2

1
1

Notes

In the first example, test case 2, there are three fair initial distributions: ~[0, 0, 0],[1, 1, 1],[2, 2, 2]~.

In the second example, test case 1 is a fair initial distribution. The process to reach every child having one candy can occur in the following order:

• Child number 4 gives one candy to child number 3 and child number 5.

• Child number 5 gives one candy to child number 4 and child number 1.

• Child number 1 gives one candy to child number 2 and child number 5.