CFCF2155C.The Ancient Wizards' Capes

有 $n$ 位巫师排成一行，从左到右编号为 $1$ 到 $n$。每位巫师都有一件隐形斗篷，可以披在他的左侧或右侧。Harry 从巫师 $1$ 的位置走到巫师 $n$ 的位置（$1 \le n \le 10^5$），并记录下他在每个巫师位置能看到多少巫师。对于每个位置 $i$，若巫师 $j$ 满足以下条件，则 $j$ 能被看到：

• 若巫师 $j$ 披在左侧，则 $i \geq j$。
• 若巫师 $j$ 披在右侧，则 $i \leq j$。

特别地，巫师 $i$ 总能被自己在第 $i$ 个位置看到。

Harry 的记录很古老，但在经过大量努力后你终于破译了这些数据。记录以长度为 $n$ 的数组 $a$ 给出，$a_i$（$1 \leq a_i \leq n$）表示 Harry 在巫师 $i$ 位置能看到的巫师数量。

你的任务是，计算所有满足 Harry 记录的可能斗篷安排的方案数，结果对 $676\,767\,677$ 取模。

每组测试包含多组用例。第一行为测试用例个数 $t$（$1 \leq t \leq 10^4$）。每组测试用例：

第一行是一个整数 $n$（$1 \leq n \leq 10^5$），表示数组 $a$ 的长度。

第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），表示 Harry 的记录。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每组测试用例，输出一个整数，表示满足条件的斗篷安排方案数，对 $676\,767\,677$ 取模。

下面的图片展示了在第二组测试用例中满足 Harry 记录的一种斗篷安排方式。

巫师 1 的斗篷披在左侧，巫师 2、3、4 的斗篷披在右侧。

• 位置 1 能看到巫师 1、2、3、4。
• 位置 2 能看到巫师 1、2、3、4。
• 位置 3 能看到巫师 1、3、4。
• 位置 4 能看到巫师 1、4。

因此 Harry 的记录为 $[4, 4, 3, 2]$。可以证明这是唯一可能的安排。

第三组测试用例中，可以证明没有任何一种斗篷安排能得到该记录。

第五组测试用例中，有两种斗篷安排符合 Harry 的记录：

• $1 \mid \quad \mid 2 \quad 3 \, \mid$
• $\mid \, 1 \quad 2 \mid \quad \mid 3$