题目描述

有 $n$ 个人排成一行，位置编号为 $1,2,\dots,n$。

给你两个整数 $n$、$m$，以及一个长度为 $n$ 的数组 $b$（$0 \le b_i < m$）。保证 $0$ 到 $m-1$ 每个数在 $b$ 中至少出现一次。

对于任意长度为 $n$ 的数组 $a$（$0 \le a_i < n$），$a_i$ 表示第 $i$ 个人的社交尴尬值。坐下规则如下：

• 若 $a_i = 0$，第 $i$ 个人在时刻 $0$ 坐下。
• 若 $a_i > 0$，第 $i$ 个人会在时刻 $t$ 开始时坐下，当且仅当同时满足：
  1. 时刻 $t$ 之前已经有至少 $a_i$ 个人坐下。
  2. 时刻 $t$ 之前至少有一个邻居（$i-1$ 或 $i+1$）已经坐下。

每一刻开始时，所有满足条件的人同时坐下。

$b_i$ 表示第 $i$ 个人必须在时刻 $b_i$ 坐下。 请你求出有多少个合法的数组 $a$ 符合要求，答案对质数 $676767677$ 取模。

输入格式

第一行一个整数 $t$，表示测试用例个数。

每个测试用例：

第一行两个整数 $n$ 和 $m$。

第二行 $n$ 个整数 $b_1,b_2,\dots,b_n$。

输出格式

对于每个测试用例，输出一行一个整数，表示合法数组 $a$ 的数量对 $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

数据规模与约定

$1 \le t \le 10^4$

$1 \le m \le n \le 2 \times 10^5$

$0 \le b_i < m$

所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

保证 $0$ 到 $m-1$ 每个数在 $b$ 中至少出现一次。

模数 $676767677$ 是质数。

来源：Codeforces Round 1090 (Div. 4) 题目网址：https://codeforces.com/contest/2218/problem/G