CFCF2207E2.N-MEX (Counting Version)

Builder Base Attack（第二阶段）——Supercell，Clash of Clans 这是该题目的计数版本。与其他版本的区别在于，本题需要统计满足 $0 \leq b_i \leq n$ 的构造方案数量。只有你完成了本题的所有版本，才可以进行 hack。

大师建筑师不喜欢重复性的任务——修补基地、升级城镇大厅十五次、还有更多关于 MEX 的编程题。所以，这不是一个普通的 MEX 题目。

对于任意正整数 $k$，定义整数集合 $S$ 的 $k$-mex 为 $S$ 中未出现的第 $k$ 小非负整数。例如，$[1, 2, 1]$ 的 $1$-mex 和 $2$-mex 分别是 $0$ 和 $3$。

给定正整数 $n$，考虑一个非负整数数组 $[a_1, \ldots, a_n]$。计算有多少个满足如下条件的非负整数数组 $[b_1, \ldots, b_n]$：

• 对所有 $1 \leq i \leq n$，$[b_1, \ldots, b_i]$ 的第 $(n-i+1)$-mex 等于 $a_i$。
• 另外，对所有 $1 \leq i \leq n$，有 $0 \leq b_i \leq n$。

由于方案数可能非常大，请输出方案数对 $10^9+7$ 取模的结果。

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

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2\times 10^5$），表示数组 $a$ 的长度。

第二行为 $n$ 个整数 $a_1, \ldots, a_n$（$0 \leq a_i \leq 10^9$）。

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

对每个测试用例，输出一个整数——满足条件的数组 $b$ 的数量，对 $10^9+7$ 取模。

在第一个测试用例中，数组 $a = [3, 3, 1]$。恰好存在六种满足条件的数组 $b$。其中一个例子是 $b = [2, 0, 2]$，其满足以下条件：

• $[b_1] = [2]$ 的 $3$-mex 等于 $a_1 = 3$；
• $[b_1, b_2] = [2, 0]$ 的 $2$-mex 等于 $a_2 = 3$；
• $[b_1, b_2, b_3] = [2, 0, 2]$ 的 $1$-mex 等于 $a_3 = 1$。

在第二个测试用例中，数组 $a = [2, 1, 3]$。可以证明不存在任何满足条件的数组 $b$。