Statement : G. The 67th Iteration of Counting is Fun

G. The 67th Iteration of "Counting is Fun"

Macaque has taken you to his habitat, shown you his job, and even forced you to do his homework for him. While it might have not been easy for you, Macaque has grown to like you and even, possibly, harbour some gratitude towards you. However, all is not finished, for Macaque has to solve his most difficult problem yet. Solving this is a matter of life or death, and determines whether Macaque can finally reach enlightenment and retreat to solitude in an organ loft for the rest of eternity. Good luck.

You are given two integers $n$ and $m$, and an array $b$ of length $n$ ($0 \le b_i \lt m$). It is guaranteed that every integer from $0$ to $m-1$ appears in $b$ at least once.

A group of $n$ people are standing in a line, in fixed positions numbered $1, 2, \dots, n$. They all want to sit down, but some are too socially awkward to do so immediately.

For some arbitrary array $a$ of length $n$ ($0 \le a_i \lt n$), each person $i$ has a social awkwardness level $a_i$. Consider the seating process which evolves in discrete units of time $0, 1, 2, \dots$ as follows:

If $a_i = 0$, person $i$ will sit down at time $0$.
Otherwise ($a_i \gt 0$), person $i$ will sit down at the beginning of a time unit $t$ if both of the following conditions are satisfied: At least $a_i$ people have already sat down strictly before time $t$.
At least one of their neighbors (person $i - 1$ or $i + 1$, if they exist) has already sat down strictly before time $t$.

At the beginning of every unit of time, each standing person checks these conditions. All people for whom the conditions are satisfied sit down simultaneously, and then the process advances to the next unit of time.

For each $i$, the value $b_i$ denotes the time unit at which person $i$ sits down. Your task is to determine how many distinct arrays $a$ are consistent with the given array $b$. Since this number can be very large, output it modulo ${\color{red}{676767677}}$.

Please note that this problem uses an unusual modulo, and that $676767677$ is prime.

Input

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The description of each test case follows:

The first line contains two integers $n$ and $m$ ($1 \le m \le n \le 2 \cdot 10^5$) — the number of people and the total duration of the process.
The second line contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i \lt m$), where $b_i$ is the time unit at which person $i$ sits down.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. It is guaranteed that each provided array $b$ contains every integer from $0$ to $m-1$.

Output

For each test case, output a single integer — the number of distinct arrays $a$ that result in the given array $b$, modulo ${\color{red}{676767677}}$.

Example

Input

7
4 3
0 1 2 0
8 4
0 1 2 3 1 2 0 1
9 5
1 0 1 3 4 3 2 1 0
15 14
3 0 1 2 3 4 5 6 7 8 9 10 11 12 13
5 5
4 3 0 1 2
5 2
0 1 1 1 0
3 2
0 1 1

Output

Note

Note

In the first test case, the only 2 valid arrays are $[0, 1, 3, 0]$ and $[0, 2, 3, 0]$. At time $0$, the $1$-st and $4$-th people sit down. Then person $2$ sits down at time $1$. If $a_2$ were $0$, person $2$ would have sat down at time $0$, and if $a_2$ were greater than $2$, person $2$ would not have been able to sit down at time $1$ since only $2$ people were sat down before time $1$. It can be shown that the only value possible for $a_3$ is $3$.

In the second test case, there are no valid arrays because it is impossible for person $5$ to sit down before either of their neighbours.