← 返回题目列表

Codeforces · 2155/C

C. 古代巫师的斗篷

中文机器翻译题面 查看原题

共有$$$n$$$ 个向导,从左到右编号为$$$1$$$ 到$$$n$$$。每个巫师都有一件隐形斗篷,可以穿在他的左侧或右侧。哈利从巫师位置 $$$1$$$ 走到巫师位置 $$$n$$$ ($$$1 \le n \le 10^5$$$),并记录他从每个巫师位置看到的巫师数量。如果满足以下条件,则位置 $$$j$$$ 中的向导从位置 $$$i$$$ 可见:

  • 巫师$$$j$$$将斗篷穿在左侧,$$$i \ge j$$$。
  • 巫师$$$j$$$将斗篷穿在右侧,$$$i \le j$$$。

特别注意,向导 $$$i$$$ 从位置 $$$i$$$ 可见。

哈利的清单很旧,但经过大量工作,你成功地破译了它。该列表是一个由 $$$n$$$ 元素组成的数组 $$$a$$$,其中第 $$$i$$$ 个元素 $$$a_i$$$ ($$$1 \le a_i \le n$$$) 是哈利从巫师 $$$i$$$ 的位置看到的巫师数量。

你的任务是确定哈利可能看到的所有可能的海角排列中有多少与列表记录的数据一致,以 $$$676\,767\,677$$$ 为模。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — $$$a$$$ 的元素。

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

输出

对于每个测试用例,打印一个整数 - 满足条件的巫师斗篷的排列数量,以 $$$676\,767\,677$$$ 为模。

示例

输入
复制

7
1
1
4
4 4 3 2
3
1 3 2
2
2 1
3
2 2 2
3
3 2 3
3
3 2 2

输出
复制

2
1
0
1
2
0
0

注意

下图显示了与哈利在第二个测试用例中的列表相匹配的斗篷排列。

巫师 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$$$