Consider an array A of length N. You know that for all 1 ≤ i ≤ N, 0 ≤ A_{i} ≤ 10^{5}. We construct an array B of length N-1 such that, for all 1 ≤ i ≤ N - 1, B_{i} = min(A_{i}, A_{i + 1}).

You are given the array B, you need to find out the total number of distinct arrays A which we could have used to construct the given array B.

The answer may be large, so you need to find it modulo 10^{9} + 7.

------ Input Format ------ 

- First line will contain T, number of testcases. Then the testcases follow.
- The first line of each test case contains a single integer N
- The second line of each test case contains N-1 space separated integers - the i^{th} of which is B_{i}

------ Output Format ------ 

For each testcase(in a new line), output the count of valid possibilities of array A modulo 10^{9} + 7.

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

$1 ≤ T ≤ 10$
$2 ≤ N ≤ 10^{5}$
$0 ≤ B_{i} ≤ 10^{5}$

----- Sample Input 1 ------ 
3
2
100
5
3 9 8 4
3
10 12
----- Sample Output 1 ------ 
199801
199983
199977
----- explanation 1 ------ 
Test Case $1$: All valid arrays $A$ are of the form $[100, x]$ and $[x, 100]$ where $100 ≤ x ≤ 10^{5}$. Therefore, the answer is $(10^{5} - 100) + (10^{5} - 100 + 1) = 199801$.

Test Case $3$: All valid arrays $A$ are of the form $[10, 12, x]$ and $[10, x, 12]$ where $12 ≤ x ≤ 10^{5}$. Therefore, the answer is $(10^{5} - 12) + (10^{5} - 12 + 1) = 199977$.

Difficulty: VERY_HARD

Starter code:

Solutions:
m = 10 ** 5
p = 10 ** 9 + 7

def solve():
	n = int(input())
	b = [0] + list(map(int, input().split()))
	f = [0] * n
	g = [0] * n
	f[1] = 1
	g[1] = m - b[1]
	for i in range(2, n):
		g[i] = f[i - 1] * (m - max(b[i - 1], b[i] + 1) + 1)
		if b[i - 1] > b[i]:
			g[i] += g[i - 1]
		elif b[i - 1] == b[i]:
			f[i] = f[i - 1] + g[i - 1]
		else:
			f[i] = f[i - 1]
		g[i] %= p
		f[i] %= p
	ans = g[n - 1] + f[n - 1] * (m - b[n - 1] + 1)
	ans %= p
	print(ans)
for t in range(int(input())):
	solve()


t = int(input())
mod = 1000000007
for tc in range(t):
	n = int(input())
	n -= 1
	arr = list(map(int, input().split()))
	dp = [[0 for i in range(2)] for j in range(n)]
	(dp[0][0], dp[0][1]) = (1, 100000 - arr[0])
	for i in range(1, n):
		if arr[i] >= arr[i - 1]:
			dp[i][0] += dp[i - 1][0]
		if arr[i] == arr[i - 1]:
			dp[i][0] += dp[i - 1][1]
		if arr[i] < arr[i - 1]:
			dp[i][1] += dp[i - 1][1]
		dp[i][1] += min(100000 - arr[i - 1] + 1, 100000 - arr[i]) * dp[i - 1][0]
		dp[i][0] %= mod
		dp[i][1] %= mod
	ans = dp[n - 1][1] + dp[n - 1][0] * (100000 - arr[n - 1] + 1)
	ans %= mod
	print(ans)


def il():
	return list(map(int, input().split()))

def ii():
	return int(input())

def imi():
	return map(int, input().split())

def ist():
	return input()
m = 10 ** 5
p = 1000000007
t = ii()
for _ in range(t):
	n = ii()
	b = [0] + il()
	f = [0] * n
	g = [0] * n
	f[1] = 1
	g[1] = m - b[1]
	for i in range(2, n):
		g[i] = f[i - 1] * (m + 1 - max(b[i - 1], b[i] + 1))
		if b[i - 1] > b[i]:
			f[i] = 0
			g[i] += g[i - 1]
		elif b[i - 1] == b[i]:
			f[i] = f[i - 1] + g[i - 1]
		else:
			f[i] = f[i - 1]
		g[i] %= p
		f[i] %= p
	x = (g[n - 1] + f[n - 1] * (m - b[n - 1] + 1)) % p
	print(x)


MOD = 10 ** 9 + 7
MAX = 10 ** 5
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	dp = [[0 for j in range(2)] for i in range(n)]
	dp[0][0] = 1
	dp[0][1] = MAX - b[0]
	for i in range(1, n - 1):
		if b[i] > b[i - 1]:
			dp[i][0] = dp[i - 1][0]
		elif b[i] < b[i - 1]:
			dp[i][0] = 0
		else:
			dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD
		if b[i] < b[i - 1]:
			dp[i][1] = (dp[i - 1][1] + dp[i - 1][0] * (MAX - b[i - 1] + 1)) % MOD
		elif b[i] > b[i - 1]:
			dp[i][1] = dp[i - 1][0] * (MAX - b[i]) % MOD
		else:
			dp[i][1] = dp[i - 1][0] * (MAX - b[i - 1]) % MOD
	print((dp[n - 2][1] + dp[n - 2][0] * (MAX - b[n - 2] + 1)) % MOD)


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(10 ** 6)
mod = 10 ** 9 + 7

def mul(a, b):
	return a % mod * (b % mod) % mod

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

def solve(i, took):
	if i == n - 1:
		if took == 1:
			return 100000 - b[i - 1] + 1
		else:
			return 1
	if dp[i][took] != -1:
		return dp[i][took]
	ans = 0
	if took == 0:
		if b[i - 1] > b[i]:
			ans = add(ans, solve(i + 1, 0))
		if b[i - 1] == b[i]:
			ans = add(ans, solve(i + 1, 1))
	else:
		if i == 0 or b[i - 1] <= b[i]:
			ans = add(ans, solve(i + 1, 1))
		if i == 0:
			x = 100000 - b[0]
		elif b[i - 1] > b[i]:
			x = 100000 - b[i - 1] + 1
		else:
			x = 100000 - b[i]
		ans = add(ans, mul(x, solve(i + 1, 0)))
	dp[i][took] = ans
	return ans

def answer():
	ans = solve(0, 1)
	return ans
for T in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	dp = [[-1, -1] for i in range(n + 1)]
	print(answer())


t = int(input())
MOD = 1000000007
MAX = 100000
while t > 0:
	n = int(input())
	b = list(map(int, input().split()))
	dp = []
	for i in range(n):
		row = []
		for j in range(2):
			row.append(0)
		dp.append(row)
	dp[0][0] = 1
	dp[0][1] = MAX - b[0]
	for i in range(1, n - 1):
		if b[i] > b[i - 1]:
			dp[i][0] = dp[i - 1][0]
		elif b[i] < b[i - 1]:
			dp[i][0] = 0
		else:
			dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD
		if b[i] < b[i - 1]:
			dp[i][1] = (dp[i - 1][1] + dp[i - 1][0] * (MAX - b[i - 1] + 1)) % MOD
		elif b[i] > b[i - 1]:
			dp[i][1] = dp[i - 1][0] * (MAX - b[i]) % MOD
		else:
			dp[i][1] = dp[i - 1][0] * (MAX - b[i - 1]) % MOD
	ans = (dp[n - 2][1] + dp[n - 2][0] * (MAX - b[n - 2] + 1)) % MOD
	print(ans)
	t -= 1


import sys
from bisect import bisect_right as lb
from collections import deque
sys.setrecursionlimit(10 ** 8)
from queue import PriorityQueue as pq
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7

def find(i, j):
	if i == n - 1:
		if j == 1:
			return 1
		return 10 ** 5 - a[i - 1] + 1
	if dp[i][j] != -1:
		return dp[i][j]
	dp[i][j] = 0
	if j == 0:
		if a[i] >= a[i - 1]:
			dp[i][j] += find(i + 1, 0)
		if a[i] >= a[i - 1]:
			dp[i][j] += find(i + 1, 1) * (10 ** 5 - a[i])
		else:
			dp[i][j] += find(i + 1, 1) * (10 ** 5 - a[i - 1] + 1)
	elif a[i] < a[i - 1]:
		dp[i][j] += find(i + 1, 1)
	elif a[i] == a[i - 1]:
		dp[i][j] += find(i + 1, 0)
	dp[i][j] %= mod
	return dp[i][j]
for _ in range(ii()):
	n = ii()
	a = il()
	dp = [[-1, -1] for i in range(n + 3)]
	print((find(1, 0) + find(1, 1) * (10 ** 5 - a[0])) % mod)