题目描述

有 $n$ 个人站成一排。未知数组 $a$ 满足 $0\le a_i<n$，若 $a_i=0$ 则第 $i$ 人在时间 $0$ 坐下；否则在某时刻开始时，若此前已坐下人数至少为 $a_i$，且至少一个相邻的人已坐下，则该人坐下。给定每个人坐下时间 $b_i$，求有多少个数组 $a$ 能产生该 $b$，答案模 $676767677$。

输入格式

第一行整数 $t$。每组第一行 $n,m$，第二行 $n$ 个整数 $b_i$，且 $0$ 到 $m-1$ 都出现。

输出格式

每组输出合法数组数量。

样例

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 m\le n\le2\cdot10^5$，所有测试 $n$ 之和不超过 $2\cdot10^5$。

来源

Codeforces Round 1090 (Div. 4), Problem G - The 67th Iteration of "Counting is Fun"