CF2259H Treasure Map Destruction (Counting Version)

海盗 Bessie 多年来在六七个大海里劫掠，如今她需要找个地方埋藏宝藏！ 有 $n$ 个岛屿排成一行，Bessie 在若干个岛屿上埋下了宝藏。保证至少有一个岛屿埋有宝藏。 为了记住她藏宝藏的位置，她制作了一张藏宝图。这张藏宝图可以表示为一个长度为 $n$ 的整数数组，其中 $a_i$ 表示如果 Bessie 从第 $i$ 个岛屿出发，仅能前往相邻的岛屿，那么到达最近一个有宝藏的岛屿最少需要经过的岛屿数。 然而，在 Bessie 埋好宝藏后，邪恶的探险家 Elsie 试图偷走藏宝图！幸运的是，Elsie 没有得逞，但在混乱中，藏宝图的部分内容被破坏，导致某些 $a$ 数组中的元素被设置为 $-1$！惊慌之下，Bessie 把损坏后的数组 $b$ 交给你，并想知道她将宝藏藏在哪里存在多少种可能的不同岛屿集合。若 $A, B$ 是两个集合，且存在至少一个元素在 $A$ 而不在 $B$ 或在 $B$ 而不在 $A$，则认为这两个集合是不同的。 Bessie 画藏宝图的时候可能会犯错，所以也有可能不存在任何岛屿分布方案。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$）——表示岛屿的数量。 第二行包含 $b_1, b_2, \ldots, b_n$（$-1 \leq b_i \leq n-1$）——表示被破坏的距离数组。如果 $b_i = -1$，则表示该元素被破坏。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出 Bessie 可能埋藏宝藏的不同岛屿集合数，结果对 $10^9 + 7$ 取模。

在第一个测试用例中，我们知道 Bessie 在第一个和第五个岛屿上都埋了宝藏，但第三、第四个岛屿 Bessie 也可以埋宝藏，导致满足条件的方案分别是：只在第1和第5岛、在第1、3和5岛、在第1、4和5岛、在第1、3、4和第5岛，总共4种可能方案。 在第四个测试用例中，藏宝图全部被破坏，所以所有 $2^5-1=31$ 个非空岛屿集合都是可能的。 由 ChatGPT 5 翻译