You are given an array of integers $b_1, b_2, \ldots, b_n$.

An array $a_1, a_2, \ldots, a_n$ of integers is hybrid if for each $i$ ($1 \leq i \leq n$) at least one of these conditions is true:

$b_i = a_i$, or

$b_i = \sum_{j=1}^{i} a_j$.

Find the number of hybrid arrays $a_1, a_2, \ldots, a_n$. As the result can be very large, you should print the answer modulo $10^9 + 7$.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($-10^9 \le b_i \le 10^9$).

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


-----Output-----

For each test case, print a single integer: the number of hybrid arrays $a_1, a_2, \ldots, a_n$ modulo $10^9 + 7$.


-----Examples-----

Input
4
3
1 -1 1
4
1 2 3 4
10
2 -1 1 -2 2 3 -5 0 2 -1
4
0 0 0 1
Output
3
8
223
1


-----Note-----

In the first test case, the hybrid arrays are $[1, -2, 1]$, $[1, -2, 2]$, $[1, -1, 1]$.

In the second test case, the hybrid arrays are $[1, 1, 1, 1]$, $[1, 1, 1, 4]$, $[1, 1, 3, -1]$, $[1, 1, 3, 4]$, $[1, 2, 0, 1]$, $[1, 2, 0, 4]$, $[1, 2, 3, -2]$, $[1, 2, 3, 4]$.

In the fourth test case, the only hybrid array is $[0, 0, 0, 1]$.

Difficulty: VERY_HARD
Tags: Dynamic programming

Sorting

Data structures

Combinatorics
Skill types: Dynamic programming

Sorting

Data structures

Starter code:

Solutions:
from collections import defaultdict
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	B = list(map(int, input().split()))
	dp = defaultdict(int)
	(cur, ans) = (0, 0)
	for (i, b) in enumerate(B):
		v = 1 if not i else (ans - dp[cur]) % mod
		ans = (ans + v) % mod
		dp[cur] = (dp[cur] + v) % mod
		cur += b
	print(ans)


import sys
import math

def II():
	return int(sys.stdin.readline())

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

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()

def FACT(n, mod):
	s = 1
	facts = [1]
	for i in range(1, n + 1):
		s *= i
		s %= mod
		facts.append(s)
	return facts[n]

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
mod = 10 ** 9 + 7
for _ in range(II()):
	n = II()
	b = LI()
	d = {}
	dp = [0 for i in range(n + 1)]
	dp[0] = 1
	d[0] = 1
	s = 0
	for i in range(n):
		dp[i + 1] = (dp[i] * 2 - d.get(s, 0) + mod) % mod
		d[s] = dp[i]
		s += b[i]
	print(dp[-1])


import sys
input = sys.stdin.readline
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	mod = 10 ** 9 + 7
	dp = defaultdict(int)
	dp[0] = 1
	ans = 1
	cur = 0
	for a in A:
		extra = dp[cur]
		dp[cur] = ans
		cur -= a
		ans = (2 * ans - extra) % mod
	print(ans)


for s in [*open(0)][2::2]:
	C = [0]
	D = {0: 1}
	S = 1
	for n in map(int, s.split()):
		C += (C[-1] + n,)
	for n in C[1:-1]:
		(D[n], S) = (S, (2 * S - D.get(n, 0)) % (10 ** 9 + 7))
	print(S)


p = lambda : list(map(int, input().split()))
for t in range(p()[0]):
	N = p()[0]
	B = p()
	C = [0] * (N + 1)
	for i in range(N):
		C[i + 1] = C[i] + B[i]
	S = 1
	D = dict()
	D[0] = 1
	for i in range(1, N):
		(D[C[i]], S) = (S, (2 * S - D.get(C[i], 0)) % (10 ** 9 + 7))
	print(S)


import sys
from sys import stdin
mod = 10 ** 9 + 7
tt = int(stdin.readline())
for loop in range(tt):
	n = int(stdin.readline())
	b = [0] + list(map(int, stdin.readline().split()))
	c = [0]
	for i in range(1, n + 1):
		c.append(c[-1] + b[i])
	dic = {}
	dic[0] = 1
	ds = 1
	for i in range(1, n + 1):
		nc = c[i - 1]
		if nc not in dic:
			last = 0
		else:
			last = dic[nc]
		dic[nc] = ds
		ds -= last
		ds += dic[nc]
		ds %= mod
	print(ds % mod)


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		n = int(input())
		b = list(map(int, input().split()))
		MOD = 10 ** 9 + 7
		DP = [0] * n
		DP[0] = 1
		sumDictionary = {0: 1}
		curSum = b[0]
		for i in range(1, n):
			if curSum in sumDictionary:
				DP[i] = 2 * DP[i - 1] - DP[sumDictionary[curSum] - 1]
				sumDictionary[curSum] = i
			else:
				DP[i] = 2 * DP[i - 1]
				sumDictionary[curSum] = i
			curSum += b[i]
			DP[i] %= MOD
		print(DP[-1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt, log2
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

def solve(case):
	n = int(inp())
	b = lis()
	dp = [0] * (n + 1)
	dp[0] = 1
	help = [0] * (n + 1)
	if b[0] == 0:
		help[0] = 1
	curr = b[0]
	pref = {0: 0, curr: 0}
	for i in range(1, n):
		curr += b[i]
		dp[i] = 2 * dp[i - 1]
		dp[i] -= help[i - 1]
		dp[i] %= mod
		if curr in pref:
			help[i] = dp[pref[curr]]
		pref[curr] = i
	print(dp[n - 1] % mod)
testcase(int(inp()))


def solve():
	MOD = 10 ** 9 + 7
	n = int(input())
	a = [int(t) for t in input().split()]
	p = [1]
	q = [0]
	psums = {0: 0}
	s = 0
	for i in range(n):
		s += a[i]
		if s in psums:
			j = psums[s]
			x = (p[j] + q[j]) % MOD
		else:
			x = 0
		psums[s] = i + 1
		p.append(x)
		q.append((p[i] + q[i] * 2 - x) % MOD)
	print((p[-1] + q[-1]) % MOD)
import sys, os, io
input = lambda : sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode('ascii'))
for _ in range(int(input())):
	solve()
os.write(1, stdout.getvalue())


import sys, os
if os.environ['USERNAME'] == 'kissz':
	inp = open('in.txt', 'r').readline

	def debug(*args):
		print(*args, file=sys.stderr)
else:
	inp = sys.stdin.readline

	def debug(*args):
		pass
for _ in range(int(inp())):
	n = int(inp())
	(offset, *B) = map(int, inp().split())
	presum_list = {0: 1}
	total = 1
	for b in B:
		if -offset not in presum_list.keys():
			presum_list[-offset] = 0
		zeros = presum_list[-offset]
		presum_list[-offset] = total
		total = (2 * total - zeros) % 1000000007
		offset += b
	print(total)


T = int(input())
for t in range(T):
	n = int(input())
	bb = [int(x) for x in input().split()]
	sums_bef_offset = {bb[0]: 1}
	offset = 0
	all_sums = 1
	base = 1000000007
	result = 0
	for i in range(1, n):
		b = bb[i]
		sums_0 = sums_bef_offset.get(-offset, 0)
		offset += b
		prev_all_sums = all_sums
		sums_bef_offset[b - offset] = prev_all_sums
		all_sums = (2 * prev_all_sums - sums_0) % base
	print(all_sums)


import sys
mod = 10 ** 9 + 7
for t in range(int(input())):
	N = int(input())
	B = list(map(int, input().split()))
	C = [0] * (N + 1)
	for i in range(N):
		C[i + 1] = C[i] + B[i]
	S = 1
	D = dict()
	D[0] = 1
	for i in range(N - 1):
		T = (S + S - D.get(C[i + 1], 0)) % mod
		D[C[i + 1]] = S
		S = T
	print(S)


import sys
from sys import stdin
mod = 10 ** 9 + 7

class SegTree:

	def __init__(self, N, first):
		self.NO = 2 ** (N - 1).bit_length()
		self.First = first
		self.data = [first] * (2 * self.NO)

	def calc(self, l, r):
		return (l + r) % mod

	def update(self, ind, x):
		ind += self.NO - 1
		self.data[ind] = x
		while ind >= 0:
			ind = (ind - 1) // 2
			self.data[ind] = self.calc(self.data[2 * ind + 1], self.data[2 * ind + 2])

	def query(self, l, r):
		L = l + self.NO
		R = r + self.NO
		s = self.First
		while L < R:
			if R & 1:
				R -= 1
				s = self.calc(s, self.data[R - 1])
			if L & 1:
				s = self.calc(s, self.data[L - 1])
				L += 1
			L >>= 1
			R >>= 1
		return s

	def get(self, ind):
		ind += self.NO - 1
		return self.data[ind]
tt = int(stdin.readline())
for loop in range(tt):
	n = int(stdin.readline())
	b = [0] + list(map(int, stdin.readline().split()))
	c = [0]
	for i in range(1, n + 1):
		c.append(c[-1] + b[i])
	ctoi = {}
	tlis = []
	for i in range(len(c)):
		if c[i] not in ctoi:
			ctoi[c[i]] = 0
			tlis.append(c[i])
	tlis.sort()
	for i in range(len(tlis)):
		ctoi[tlis[i]] = i
	ST = SegTree(len(tlis), 0)
	ST.update(ctoi[0], 1)
	for i in range(1, n + 1):
		ind = ctoi[c[i - 1]]
		ST.update(ind, ST.query(0, len(tlis)))
	print(ST.query(0, len(tlis)))


import collections
import string
import math
import copy
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def input():
	return sys.stdin.readline().rstrip('\r\n')
mo = int(1000000000.0 + 7)

def exgcd(a, b):
	if not b:
		return (1, 0)
	(y, x) = exgcd(b, a % b)
	y -= a // b * x
	return (x, y)

def getinv(a, m):
	(x, y) = exgcd(a, m)
	return --1 if x == 1 else x % m

def comb(n, b):
	res = 1
	b = min(b, n - b)
	for i in range(b):
		res = res * (n - i) * getinv(i + 1, mo) % mo
	return res % mo

def quickpower(a, n):
	res = 1
	while n:
		if n & 1:
			res = res * a % mo
		n >>= 1
		a = a * a % mo
	return res

def dis(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])

def getpref(x):
	if x > 1:
		return x * (x - 1) >> 1
	else:
		return 0

def orafli(upp):
	primes = []
	marked = [False for i in range(upp + 3)]
	for i in range(2, upp):
		if not marked[i]:
			primes.append(i)
		for j in primes:
			if i * j >= upp:
				break
			marked[i * j] = True
			if i % j == 0:
				break
	return primes

def solve():
	n = int(input())
	l = [int(i) for i in input().split()]
	d = {0: 1}
	tt = 1
	k = 0
	for i in range(1, 1 + n):
		a = d.setdefault(k, 0)
		d[k] = tt
		k -= l[i - 1]
		tt = (2 * tt - a) % mo
	print(tt)
t = int(input())
for ti in range(t):
	solve()


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
try:
	(sys.stdin, sys.stdout) = (open('in.txt', 'r'), open('out.txt', 'w'))
except:
	pass
ii1 = lambda : int(sys.stdin.readline().strip())
is1 = lambda : sys.stdin.readline().strip()
iia = lambda : list(map(int, sys.stdin.readline().strip().split()))
isa = lambda : sys.stdin.readline().strip().split()
mod = int(1000000000.0 + 7)
from collections import *
from math import *

def solve():
	n = ii1()
	arr = iia()
	dp = defaultdict(int)
	sumofdp = 0
	currsum = 0
	for i in range(n):
		if i == 0:
			v = 1
		else:
			v = (sumofdp - dp[currsum]) % mod
		sumofdp += v
		dp[currsum] = (dp[currsum] + v) % mod
		currsum += arr[i]
	print(sumofdp % mod)
for _ in range(ii1()):
	solve()