G. 67-я итерация "Считать всегда весело"
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Macaque привёл вас в свою среду обитания, показал вам свою работу и даже заставил делать за него домашнее задание. Хотя вам это, возможно, далось нелегко, Macaque проникся к вам симпатией и, возможно, даже испытывает некоторую благодарность. Однако ещё не всё закончено, ведь ему предстоит решить свою самую трудную задачу. Её решение — вопрос жизни и смерти, и именно оно определит, сможет ли Macaque наконец достичь просветления и удалиться в уединение на органные хоры до конца вечности. Удачи.

Вам даны два целых числа $$$n$$$ и $$$m$$$, а также массив $$$b$$$ длины $$$n$$$ ($$$0 \le b_i \lt m$$$). Гарантируется, что каждое целое число от $$$0$$$ до $$$m-1$$$ встречается в $$$b$$$ хотя бы один раз.

Группа из $$$n$$$ человек стоит в ряд на фиксированных позициях с номерами $$$1, 2, \dots, n$$$. Все они хотят сесть, но некоторые слишком социально неловки, чтобы сделать это сразу.

Для некоторого произвольного массива $$$a$$$ длины $$$n$$$ ($$$0 \le a_i \lt n$$$) у каждого человека $$$i$$$ есть уровень социальной неловкости $$$a_i$$$. Рассмотрим процесс рассаживания, который развивается в целые моменты времени $$$0, 1, 2, \dots$$$ следующим образом:

  • Если $$$a_i = 0$$$, человек $$$i$$$ сядет в момент времени $$$0$$$.
  • Иначе ($$$a_i \gt 0$$$), человек $$$i$$$ сядет в начале некоторого момента времени $$$t$$$, если выполнены оба следующих условия:
    1. По крайней мере $$$a_i$$$ человек уже сели строго раньше момента времени $$$t$$$.
    2. По крайней мере один из его соседей (человек $$$i - 1$$$ или $$$i + 1$$$, если он существует) уже сел строго раньше момента времени $$$t$$$.

В начале каждого момента времени каждый всё ещё стоящий человек проверяет эти условия. Все люди, для которых условия выполнены, садятся одновременно, после чего процесс переходит к следующему моменту времени.

Для каждого $$$i$$$ значение $$$b_i$$$ обозначает момент времени, в который человек $$$i$$$ садится. Ваша задача — определить, сколько различных массивов $$$a$$$ согласуются с данным массивом $$$b$$$. Так как это число может быть очень большим, выведите его по модулю $$${\color{red}{676767677}}$$$.

Обратите внимание, что в этой задаче используется необычный модуль, и число $$$676767677$$$ является простым.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Описание каждого набора входных данных:

  • Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le m \le n \le 2 \cdot 10^5$$$) — количество людей и общую длительность процесса.
  • Вторая строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i \lt m$$$), где $$$b_i$$$ — момент времени, в который человек $$$i$$$ садится.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$. Гарантируется, что каждый данный массив $$$b$$$ содержит все целые числа от $$$0$$$ до $$$m-1$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество различных массивов $$$a$$$, которые приводят к данному массиву $$$b$$$, по модулю $$${\color{red}{676767677}}$$$.

Пример
Входные данные
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
Выходные данные
2
0
1920
138007136
8
0
0
Примечание

В первом наборе входных данных существуют только 2 корректных массива: $$$[0, 1, 3, 0]$$$ и $$$[0, 2, 3, 0]$$$. В момент времени $$$0$$$ садятся $$$1$$$-й и $$$4$$$-й люди. Затем человек $$$2$$$ садится в момент времени $$$1$$$. Если бы $$$a_2$$$ было равно $$$0$$$, человек $$$2$$$ сел бы в момент времени $$$0$$$, а если бы $$$a_2$$$ было больше $$$2$$$, человек $$$2$$$ не смог бы сесть в момент времени $$$1$$$, так как до момента времени $$$1$$$ сели только $$$2$$$ человека. Можно показать, что единственное возможное значение для $$$a_3$$$ — это $$$3$$$.

Во втором наборе входных данных корректных массивов нет, потому что человек $$$5$$$ не может сесть раньше любого из своих соседей.