Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef is playing a new computer game in which he is the chef of a restaurant and is required to prepare the dishes ordered by the customers with high quality and in time.

Chef will start in level 1 and whenever Chef passes a level in this game he will advance to the next level, but if Chef fails, he will return to level 1.

Chef has already played N rounds, but he can't remember what the levels were in all the rounds. He will give you an array A of length N such that A_{i} is equal to -1 if Chef can't remember what level the i-th round was, otherwise it will contain positive integer denoting the level of the round.

Now Chef is asking you to count the number of ways to fill the missing numbers (ie. the -1s) of the array with level numbers, so that it corresponds to a valid game. Since the answer can be large, output it modulo 10^{9}+7.

------ Input ------ 

First line contains an integer T, the number of test-cases.

First line of each test-case contains an integer N.

Second line contains N space-separated integers, which are the elements of the array A.

------ Output ------ 

Output the answer for each test-case in new line, the number of ways modulo  10^{9}+7.

------ Constraints ------ 

$1 ≤ T ≤ 10,000$
$1 ≤ N ≤ 100,000$
$sum of N in all test-cases will not exceed 100,000$
$1 ≤ A_{i} ≤ N or A_{i} = -1$

----- Sample Input 1 ------ 
1
6
1 1 2 -1 -1 2
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
The only two valid fully filled arrays are (1,1,2,3,1,2) and (1,1,2,1,1,2). Hence the answer is 2.

Difficulty: VERY_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]

	def solve():
		for i in range(n - 1, 0, -1):
			if l[i] != -1 and l[i] != 1:
				peeche_must_be = l[i] - 1
				peeche = l[i - 1]
				if peeche == -1:
					l[i - 1] = peeche_must_be
				elif peeche != peeche_must_be:
					return 0
		if l[0] != -1 and l[0] != 1:
			return 0
		ans = 1
		k = 0
		for i in range(1, n):
			if l[i] == -1:
				k += 1
		return pow(2, k, MOD)
	print(solve())


from sys import stdin, stdout, exit

def listInput():
	return list(map(int, stdin.readline().split()))

def printBS(li):
	n = len(li)
	for i in range(n - 1):
		stdout.write('%d ' % li[i])
	if n != 0:
		stdout.write('%d\n' % li[n - 1])

def sin():
	return stdin.readline().rstrip()

def inp():
	return int(stdin.readline())
cases = inp()
for _ in range(cases):
	n = inp()
	li = listInput()
	for i in range(n - 2, -1, -1):
		if li[i] == -1 and li[i + 1] > 1:
			li[i] = li[i + 1] - 1
	pa = True
	for i in range(n - 1):
		if li[i + 1] > 1 and li[i] + 1 != li[i + 1]:
			pa = False
			break
	if not pa or li[0] not in (-1, 1):
		print(0)
		continue
	if li[0] == -1:
		li[0] = 1
	MOD = 10 ** 9 + 7
	ans = 1
	for i in range(n):
		if li[i] == -1:
			ans = ans * 2 % MOD
	print(ans)


def fast_exp(k):
	if k == 0:
		return 1
	elif k == 1:
		return 2
	elif k % 2 == 0:
		x = fast_exp(k // 2) % 1000000007
		return x * x % 1000000007
	else:
		x = fast_exp(k // 2) % 1000000007
		return 2 * x * x % 1000000007
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = True
	k = 0
	if a[0] == -1:
		a[0] = 1
	elif a[0] > 1:
		f = False
	for i in range(n - 1, 0, -1):
		if a[i] <= 1:
			continue
		elif a[i] != 1:
			if a[i - 1] != a[i] - 1 and a[i - 1] != -1:
				f = False
				continue
			elif a[i - 1] == -1:
				a[i - 1] = a[i] - 1
	if a[0] > 1:
		f = False
	if not f:
		print(0)
	else:
		print(fast_exp(a.count(-1)))


import io
import sys

def test_data(limit_n):
	s = '9\n6\n1 1 2 -1 -1 2\n3\n-1 3 1\n4\n-1 -1 3 1\n4\n1 2 3 4\n4\n4 3 2 1\n5\n-1 -1 -1 -1 2\n9\n-1 -1 -1 -1 2 -1 -1 -1 3\n11\n-1 -1 -1 -1 2 -1 -1 -1 3 -1 -1\n'
	s += '{n}\n{ints}\n'.format(n=limit_n, ints=' '.join(['-1'] * limit_n))
	return io.StringIO(s)

def get_input(source):
	with source as lines:
		t = int(next(lines))
		for _ in range(t):
			n = int(next(lines))
			levels = list(map(int, next(lines).split(' ')))
			yield (n, levels)

def calc(n, levels):
	if levels[0] == -1:
		levels[0] = 1
	elif levels[0] != 1:
		return 0
	prev = 1
	for i in range(len(levels), 0, -1):
		i -= 1
		level = levels[i]
		if prev != 1:
			expected = prev - 1
			if level == -1:
				level = expected
				levels[i] = expected
			elif level != expected:
				return 0
		prev = max(level, 1)
	if prev != 1:
		return 0
	prev = 1
	blanks = 0
	solutions = 1
	for level in levels:
		if level != -1:
			if blanks != 0:
				solutions *= 2 ** blanks
				blanks = 0
			prev = level
			continue
		blanks += 1
	if blanks != 0:
		solutions *= 2 ** blanks
	return solutions % (10 ** 9 + 7)
limit_n = 100000
inp = test_data(limit_n) if '-test' in sys.argv else sys.stdin
for args in get_input(inp):
	print(calc(*args))


m = 10 ** 9 + 7
p2 = [1] * 100005
for i in range(1, len(p2)):
	p2[i] = p2[i - 1] * 2 % m
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = [-100] + a + [1]
	if a[1] == -1:
		a[1] = 1
	i = 1
	ans = 1
	while i < len(a) - 1:
		if a[i] > -1:
			if a[i] == 1 or a[i] == a[i - 1] + 1:
				i += 1
				continue
			else:
				ans = 0
				break
		j = i + 1
		while a[j] == -1:
			j += 1
		gap = j - i
		h1 = a[i - 1]
		h2 = a[j]
		if a[j] == 1:
			ans = ans * p2[gap] % m
		elif h2 == h1 + gap + 1:
			pass
		elif h2 > gap + 1:
			ans = 0
			break
		else:
			ans = ans * p2[gap + 1 - h2] % m
		i = j + 1
	print(ans)