Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

Ridbit is given an array $a_{1}, a_{2}, \ldots, a_{N}$. He needs to find the number of ways to divide the array into contiguous subarrays such that:
Each element of the sequence $a$ belongs to exactly one of the subarrays.
There is an integer $m$ such that the MEX of every subarray is equal to $m$. The MEX of a sequence is the smallest non-negative integer which does not occur in this sequence.

Help Ridbit with this task.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $a_{1}, a_{2}, \ldots, a_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the number of ways to divide the sequence, modulo $10^{9} + 7$.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 100,000$
$0 ≤ a_{i} ≤ N$ for each valid $i$

----- Sample Input 1 ------ 
2

6

1 0 0 1 0 1

3

1 2 3
----- Sample Output 1 ------ 
5

4
----- explanation 1 ------ 
Example case 1: The five valid ways to divide the sequence are:
- $[1, 0, 0, 1, 0, 1]$
- $[1, 0], [0, 1, 0, 1]$
- $[1, 0, 0], [1, 0, 1]$
- $[1, 0, 0, 1], [0, 1]$
- $[1, 0], [0, 1], [0, 1]$

Source: codechef | Difficulty: VERY_HARD
Tags: Combinatorics

Data structures


Solutions:
mod = 10 ** 9 + 7
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	l = sorted(arr)
	prev = -1
	for i in range(n):
		if l[i] - prev > 1:
			break
		prev = l[i]
	m = prev + 1
	d = {}
	for i in range(n):
		if arr[i] > m:
			continue
		d[arr[i]] = d.get(arr[i], 0) + 1
	p = n - 1
	while p >= 0:
		if arr[p] < m:
			if d[arr[p]] == 1:
				break
			else:
				d[arr[p]] = d[arr[p]] - 1
		p = p - 1
	p = p + 1
	p = max(1, p)
	dp = [0] * (n + 1)
	pref = [0] * (n + 1)
	dp[0] = 1
	pref[0] = 1
	for i in range(1, p):
		dp[i] = 0
		pref[i] = 1
	dp[p] = 1
	pref[p] = 2
	p = p + 1
	prev = 1
	while p <= n:
		if arr[p - 1] < m:
			d[arr[p - 1]] = d[arr[p - 1]] + 1
		while prev < p:
			if arr[prev - 1] < m:
				if d[arr[prev - 1]] == 1:
					break
				else:
					d[arr[prev - 1]] = d[arr[prev - 1]] - 1
			prev = prev + 1
		dp[p] = pref[prev - 1]
		pref[p] = (pref[p - 1] + dp[p]) % mod
		p = p + 1
	print(dp[n])


from sys import stdin
input = stdin.readline
mod = 10 ** 9 + 7

def add(a, b):
	return (a % mod + b % mod) % mod

def mexofa():
	c = [0] * (size + 1)
	for i in a:
		c[i] += 1
	for i in range(size + 1):
		if c[i] == 0:
			return i

def answer():
	if mex == 0:
		return pow(2, n - 1, mod)
	c = [0] * (size + 1)
	nextind = [-1] * n
	m = 0
	for i in range(n - 1, -1, -1):
		if a[i] == m:
			for j in range(a[i] + 1, size + 1):
				if c[j] == 0:
					m = j
					break
		c[a[i]] += 1
		if m == mex:
			nextind[n - 1] = i
			break
	need = -1
	for i in range(n - 2, -1, -1):
		c[a[i + 1]] -= 1
		if c[a[i + 1]] == 0 and a[i + 1] < mex:
			need = a[i + 1]
		if need == -1:
			nextind[i] = nextind[i + 1]
			continue
		for j in range(nextind[i + 1] - 1, -1, -1):
			c[a[j]] += 1
			if need == a[j]:
				nextind[i] = j
				break
		need = -1
	dp = [0] * (n + 1)
	pf = [0] * (n + 1)
	for i in range(1, n + 1):
		if nextind[i - 1] == -1:
			continue
		dp[i] = add(dp[i], pf[nextind[i - 1]] + 1)
		pf[i] = add(pf[i], dp[i])
		pf[i] = add(pf[i], pf[i - 1])
	return dp[n]
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	size = max(a) + 1
	mex = mexofa()
	print(answer())


def find_mex(arr):
	max_value = len(arr) + 1
	all_possibles = set(range(max_value))
	arr_values = set(arr)
	omissions = all_possibles - arr_values
	return min(omissions)

def calc_k(arr, mex):
	DP = [None] * (len(arr) + 1)
	for i in range(len(arr) + 1):
		if mex:
			DP[i] = [0, 0, 0]
		else:
			DP[i] = [1, 0, 0]
	end_pointer = 0
	start_pointer = 0
	counts = {i: 0 for i in range(mex)}
	missing_numbers = set([i for i in range(mex)])
	while end_pointer < len(arr):
		if arr[end_pointer] < mex:
			counts[arr[end_pointer]] += 1
			if counts[arr[end_pointer]] == 1:
				missing_numbers.remove(arr[end_pointer])
			while not missing_numbers:
				DP[start_pointer][0] = end_pointer - start_pointer + 1
				if arr[start_pointer] < mex:
					counts[arr[start_pointer]] -= 1
					if counts[arr[start_pointer]] == 0:
						missing_numbers.add(arr[start_pointer])
				start_pointer += 1
		end_pointer += 1
	return DP

def calc_DP(DP):
	M = 10 ** 9 + 7
	for i in range(len(arr) - 1, -1, -1):
		if testing:
			print(i, DP[i], end='')
		if DP[i][0]:
			k = DP[i][0]
			DP[i][1] = (1 + DP[i + k][2]) % M
			DP[i][2] = (DP[i][1] + DP[i + 1][2]) % M
			if testing:
				print('->', DP[i])
		elif testing:
			print()
	return DP
testing = False
if testing:
	arr = [1, 0, 0, 1, 0, 1]
	mex = find_mex(arr)
	print(arr, mex)
	DP = calc_k(arr, mex)
	print(DP)
	print(calc_DP(DP))
	arr = [1, 2, 3]
	mex = find_mex(arr)
	print(arr, mex)
	DP = calc_k(arr, mex)
	print(DP)
	print(calc_DP(DP))
T = int(input())
for tc in range(T):
	N = int(input())
	arr = [int(x) for x in input().strip().split(' ')]
	mex = find_mex(arr)
	DP = DP = calc_k(arr, mex)
	print(calc_DP(DP)[0][1])


def main():
	mod = 10 ** 9 + 7
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		xx = [0] * (n + 2)
		for i in a:
			xx[i] += 1
		if min(a):
			print(pow(2, n - 1, mod))
			continue
		for i in range(n + 2):
			if not xx[i]:
				m = i
				break
		req = [0] * m
		done = m
		dp = [-1] * n
		i = n - 1
		for j in range(n - 1, -1, -1):
			if a[j] < len(req):
				req[a[j]] += 1
				if req[a[j]] == 1:
					done -= 1
				while i != -1 and (not done):
					dp[i] = j
					if a[i] < len(req):
						req[a[i]] -= 1
						done += req[a[i]] == 0
					i -= 1
		dp1 = [0] * n
		pref = [1] + [0] * n
		for i in range(n):
			if dp[i] != -1:
				dp1[i] = pref[dp[i]]
			pref[i + 1] = (pref[i] + dp1[i]) % mod
		print(dp1[-1])
main()


import sys
T = int(input())
P = 1000000007
for t in range(T):
	N = int(input())
	A = list((int(x) for x in sys.stdin.readline().split()))
	m1 = min(A)
	if m1 > 0:
		print(pow(2, N - 1, P))
	else:
		nums = [0] * 100001
		for a in A:
			nums[a] += 1
		mex = -1
		for i in range(len(nums)):
			if nums[i] == 0:
				mex = i
				break
		T = []
		mymap = [0] * mex
		cnt = 0
		j = 0
		while j < N and cnt < mex:
			val = A[j]
			if val < mex:
				if mymap[val] == 0:
					cnt += 1
				mymap[val] += 1
			j += 1
			if cnt == mex:
				T.append(1)
				break
			else:
				T.append(0)
		if j == N:
			if cnt == mex:
				print(1)
			else:
				print(0)
		else:
			setStart = 0
			while j < N:
				while cnt == mex:
					val = A[setStart]
					if val < mex:
						mymap[val] -= 1
						if mymap[val] == 0:
							cnt -= 1
					setStart += 1
				val = A[j]
				if val < mex:
					if mymap[val] == 0:
						cnt += 1
					mymap[val] += 1
				newval = T[-1]
				if cnt == mex:
					newval += T[setStart - 1]
					newval = newval % P
					while A[setStart] < mex and mymap[A[setStart]] > 1 or A[setStart] > mex:
						if A[setStart] > mex:
							setStart += 1
							newval += T[setStart - 1]
							newval = newval % P
						else:
							mymap[A[setStart]] -= 1
							setStart += 1
							newval += T[setStart - 1]
							newval = newval % P
				T.append(newval)
				j += 1
			2
			print(T[-1])


import sys
input = sys.stdin.readline
import heapq

def solution(N, arr):
	mod_ = 10 ** 9 + 7
	last = {}
	small_missing = 0
	ferme = [0 for _ in range(N)]
	jusqua = [1 for _ in range(N)]
	h = []
	s_vals = set(arr)
	for i in range(N + 1):
		if i not in s_vals:
			small_missing = i
			break
	if small_missing == 0:
		print(pow(2, N - 1, mod_))
		return
	for (pos, elem) in enumerate(arr):
		if elem < small_missing:
			last[elem] = pos
			heapq.heappush(h, (pos, elem))
		if len(last) == small_missing:
			while h[0][0] != last[h[0][1]]:
				heapq.heappop(h)
			precedent = h[0][0] - 1
			if precedent == -1:
				ferme[pos] = 1
			else:
				ferme[pos] = jusqua[precedent]
			if pos > 0:
				jusqua[pos] = (jusqua[pos - 1] + ferme[pos]) % mod_
			else:
				jusqua[pos] = 2
	print(ferme[-1])
T = int(input())
for t in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	solution(N, arr)


T = int(input())
P = 10 ** 9 + 7
for _ in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	S = set(A)
	MEX = 0
	while True:
		if MEX not in S:
			break
		MEX += 1
	if MEX == 0:
		print(pow(2, N - 1, P))
		continue
	S1 = set(range(MEX))
	end_index = N - 1
	while True:
		if not S1:
			break
		if A[end_index] in S1:
			S1.remove(A[end_index])
		end_index -= 1
		if end_index < 0:
			break
	S1 = set(range(MEX))
	start_index = 0
	last_seen = [-1 for _ in range(MEX)]
	while True:
		if not S1:
			break
		if A[start_index] < MEX:
			last_seen[A[start_index]] = start_index
			if A[start_index] in S1:
				S1.remove(A[start_index])
		start_index += 1
		if start_index == N:
			break
	until_here = min(last_seen)
	num_ending_before = [1 for _ in range(start_index)]
	if start_index <= end_index + 1:
		num_ending_before += [2]
	for i in range(start_index, end_index + 1):
		if A[i] < MEX:
			last_seen[A[i]] = i
		while True:
			if A[until_here] >= MEX:
				until_here += 1
			elif last_seen[A[until_here]] > until_here:
				until_here += 1
			else:
				break
		num_ending_before += [(num_ending_before[until_here] + num_ending_before[-1]) % P]
	print(num_ending_before[-1])