H. Treasure Map Destruction (Counting Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bessie the Buccaneer has plundered the six or seven seas for decades, but now she needs to find a place to bury her treasure!

There are $$$n$$$ islands in a line, and Bessie buried her treasure on some number of islands. It is guaranteed that Bessie buried treasure on at least one island.

In order to remember where she buried her treasure, she created a treasure map. The treasure map can be represented as an array of $$$n$$$ integers, where $$$a_i$$$ indicates the minimum number of islands that Bessie would need to travel through to get to an island with treasure if she started at island $$$i$$$, assuming she can only travel to adjacent islands.

However, after Bessie buried her treasure, Elsie the Evil Explorer tried to steal Bessie's treasure map! Thankfully, Elsie was unsuccessful, but in the chaos, parts of Bessie's treasure map got destroyed, meaning that some of the elements of $$$a$$$ were set to $$$-1$$$! Panicked, Bessie gives you the destroyed array $$$b$$$, and wants to know how many possible distinct sets of islands she could have placed her treasures on. Two sets $$$A, B$$$ are distinct if there exists at least one element in $$$A$$$ that is not in $$$B$$$ or vice versa.

It's possible that Bessie messed up while writing the treasure map, so there could be no possible set of islands on which she could have placed her treasure.

Input

The first line of the input contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of islands.

The second line contains $$$b_1, b_2, \ldots, b_n$$$ ($$$-1 \leq b_i \leq n-1$$$) — the destroyed array of distances. If $$$b_i = -1$$$, the element was destroyed.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each testcase, output the number of possible distinct sets of islands that Bessie could have placed her treasure on mod $$$10^9 + 7$$$.

Example
Input
12
5
0 1 -1 -1 0
3
-1 0 2
5
-1 1 -1 1 -1
5
-1 -1 -1 -1 -1
5
-1 2 -1 3 -1
7
2 1 0 1 0 1 2
1
-1
3
1 -1 1
1
0
4
3 -1 -1 -1
6
-1 -1 0 -1 2 4
10
-1 1 -1 -1 1 1 -1 -1 2 -1
Output
4
0
5
31
0
1
1
1
1
1
0
3
Note

In the first test case, while we know that Bessie placed treasure at the first and fifth islands, Bessie could have also placed her treasure at the third island, fourth island, both the third and fourth islands, or neither the third nor fourth island, leading to 4 possible sets of island locations.

In the fourth test case, since the entire map was destroyed, all $$$2^5 - 1 = 31$$$ non-empty sets of islands are possible.