Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.
Since the answer may be large, return the answer modulo 10^9 + 7.
 
Example 1:
Input: [3,1,2,4]
Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.
 
Note:

1 <= A.length <= 30000
1 <= A[i] <= 30000

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        

Solutions:
class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		stack = []
		result = 0
		A = [0] + A + [0]
		for (i, x) in enumerate(A):
			while stack and x < A[stack[-1]]:
				j = stack.pop()
				result += A[j] * (i - j) * (j - stack[-1])
			stack.append(i)
		return result % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A):
		res = 0
		s = []
		A = [0] + A + [0]
		for (i, x) in enumerate(A):
			while s and A[s[-1]] > x:
				j = s.pop()
				k = s[-1]
				res += A[j] * (i - j) * (j - k)
			s.append(i)
		return res % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		MOD = 10 ** 9 + 7
		N = len(A)
		stack = []
		prev = [None] * N
		for i in range(N):
			while stack and A[i] < A[stack[-1]]:
				stack.pop()
			prev[i] = stack[-1] if stack else -1
			stack.append(i)
		stack = []
		next_ = [None] * N
		for k in range(N - 1, -1, -1):
			while stack and A[k] <= A[stack[-1]]:
				stack.pop()
			next_[k] = stack[-1] if stack else N
			stack.append(k)
		return sum(((i - prev[i]) * (next_[i] - i) * A[i] for i in range(N))) % MOD


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		previous_less = [-1] * len(A)
		p_stack = []
		next_less = [len(A)] * len(A)
		n_stack = []
		for i in range(len(A)):
			n = A[i]
			while p_stack and A[p_stack[-1]] > n:
				p_stack.pop()
			if p_stack:
				previous_less[i] = p_stack[-1]
			else:
				previous_less[i] = -1
			p_stack.append(i)
			while n_stack and A[n_stack[-1]] > n:
				x = n_stack[-1]
				n_stack.pop()
				next_less[x] = i
			n_stack.append(i)
		ans = 0
		mod = 10 ** 9 + 7
		for i in range(len(A)):
			left = i - previous_less[i]
			right = next_less[i] - i
			ans = (ans + A[i] * left * right) % mod
		return ans


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		n = len(A)
		low = [None] * n
		high = [None] * n
		stack = []
		for i in range(n):
			while stack and A[stack[-1]] >= A[i]:
				stack.pop()
			low[i] = stack[-1] if stack else -1
			stack.append(i)
		stack = []
		for i in range(n - 1, -1, -1):
			while stack and A[stack[-1]] > A[i]:
				stack.pop()
			high[i] = stack[-1] if stack else n
			stack.append(i)
		ans = 0
		for i in range(n):
			ans = (ans + (i - low[i]) * (high[i] - i) * A[i]) % int(1000000000.0 + 7)
		return ans


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		left = [0] * len(A)
		right = [0] * len(A)
		(s1, s2) = ([], [])
		for i in range(len(A)):
			count = 1
			while s1 and s1[-1][0] > A[i]:
				count += s1.pop()[1]
			s1.append([A[i], count])
			left[i] = count
		for i in range(len(A))[::-1]:
			count = 1
			while s2 and s2[-1][0] >= A[i]:
				count += s2.pop()[1]
			s2.append([A[i], count])
			right[i] = count
		ret = 0
		for i in range(len(A)):
			ret += A[i] * (left[i] * right[i])
		return ret % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		firstLessR = []
		firstLessL = []
		n = len(A)
		for i in range(n):
			firstLessR.append(i)
			firstLessL.append(i)
		incNums = []
		for i in range(n):
			if i == 0:
				incNums.append(i)
			else:
				while len(incNums) > 0 and A[incNums[-1]] >= A[i]:
					firstLessR[incNums[-1]] = i
					incNums.pop()
				incNums.append(i)
		for i in incNums:
			firstLessR[i] = n
		incNums = []
		for i in range(n - 1, -1, -1):
			if i == n - 1:
				incNums.append(i)
			else:
				while len(incNums) > 0 and A[incNums[-1]] > A[i]:
					firstLessL[incNums[-1]] = i
					incNums.pop()
				incNums.append(i)
		for i in incNums:
			firstLessL[i] = -1
		ans = 0
		for i in range(n):
			w = (firstLessR[i] - i) * (i - firstLessL[i])
			ans += w * A[i]
			ans = ans % 1000000007
		return ans


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		n = len(A)
		count = [0] * n
		s = []
		for i in range(n):
			while len(s) > 0 and A[i] <= A[s[-1]]:
				s.pop()
			if len(s) == 0:
				count[i] = i + 1
			else:
				count[i] = i - s[-1]
			s.append(i)
		s = []
		for i in range(n - 1, -1, -1):
			while len(s) > 0 and A[i] < A[s[-1]]:
				s.pop()
			if len(s) == 0:
				count[i] *= n - i
			else:
				count[i] *= s[-1] - i
			s.append(i)
		res = 0
		for i in range(n):
			res += count[i] * A[i]
		return res % 1000000007


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		MOD = 10 ** 9 + 7
		stack = []
		ans = dot = 0
		for (j, y) in enumerate(A):
			count = 1
			while stack and stack[-1][0] >= y:
				(x, c) = stack.pop()
				count += c
				dot -= x * c
			stack.append((y, count))
			dot += y * count
			ans += dot
		return ans % MOD


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		n = len(A)
		(left, right, sl, sr) = ([0] * n, [0] * n, [], [])
		for i in range(n):
			count = 1
			while sl and sl[-1][0] > A[i]:
				count += sl.pop()[1]
			left[i] = count
			sl.append([A[i], count])
		for j in range(n)[::-1]:
			count = 1
			while sr and sr[-1][0] >= A[j]:
				count += sr.pop()[1]
			right[j] = count
			sr.append([A[j], count])
		return sum((a * l * r for (a, l, r) in zip(A, left, right))) % 1000000007


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		tot = 0
		stack = [-1]
		A.append(0)
		for i in range(len(A)):
			while A[i] < A[stack[-1]]:
				loc = stack.pop()
				height = A[loc]
				left = loc - stack[-1]
				right = i - loc
				width = i - stack[-1] - 1
				tot += height * left * right
			stack.append(i)
		return tot % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		n = len(A)
		left_less = [0] * n
		right_less = [0] * n
		left_stack = []
		right_stack = []
		for i in range(n):
			count = 1
			while left_stack and left_stack[-1][0] > A[i]:
				count += left_stack.pop()[1]
			left_less[i] = count
			left_stack.append([A[i], count])
		for i in range(n - 1, -1, -1):
			count = 1
			while right_stack and right_stack[-1][0] >= A[i]:
				count += right_stack.pop()[1]
			right_less[i] = count
			right_stack.append([A[i], count])
		mod = 10 ** 9 + 7
		return sum((A[i] * right_less[i] * left_less[i] for i in range(n))) % mod


class Solution(object):

	def sumSubarrayMins(self, A):
		MOD = 10 ** 9 + 7
		N = len(A)
		stack = []
		prev = [None] * N
		for i in range(N):
			count = 1
			while stack and A[i] <= A[stack[-1][0]]:
				(x, c) = stack.pop()
				count += c
			stack.append((i, count))
			prev[i] = stack[-1][1] if stack else -1
		print(prev)
		stack = []
		nxt = [None] * N
		for k in range(N - 1, -1, -1):
			count = 1
			while stack and A[k] < A[stack[-1][0]]:
				(x, c) = stack.pop()
				count += c
			stack.append((k, count))
			nxt[k] = stack[-1][1] if stack else N
		print(nxt)
		return sum((prev[i] * nxt[i] * A[i] for i in range(N))) % MOD


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		(n, mod) = (len(A), 10 ** 9 + 7)
		(left, right, stack1, stack2) = ([0] * n, [0] * n, [], [])
		for i in range(n):
			count = 1
			while stack1 and stack1[-1][0] > A[i]:
				count += stack1.pop()[1]
			left[i] = count
			stack1.append([A[i], count])
		for i in range(n - 1, -1, -1):
			count = 1
			while stack2 and stack2[-1][0] >= A[i]:
				count += stack2.pop()[1]
			right[i] = count
			stack2.append([A[i], count])
		return sum((a * l * r for (a, l, r) in zip(A, left, right))) % mod


class Solution(object):

	def sumSubarrayMins(self, A):
		MOD = 10 ** 9 + 7
		n = len(A)
		stack = []
		left = [-1] * n
		for i in range(n):
			while stack and A[i] <= A[stack[-1]]:
				stack.pop()
			if stack:
				left[i] = stack[-1]
			stack.append(i)
		stack = []
		right = [n] * n
		for k in range(n - 1, -1, -1):
			while stack and A[k] < A[stack[-1]]:
				stack.pop()
			if stack:
				right[k] = stack[-1]
			stack.append(k)
		return sum(((i - left[i]) * (right[i] - i) * A[i] for i in range(n))) % MOD


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		res = [0] * (len(A) + 1)
		A = [0] + A
		stack = [(0, 0)]
		for (i, num) in enumerate(A):
			while stack and stack[-1][0] > num:
				stack.pop()
			j = stack[-1][1]
			res[i] = res[j] + (i - j) * num
			stack.append((num, i))
		return sum(res) % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		n = len(A)
		left = [0] * n
		right = [0] * n
		s = []
		for i in range(n):
			count = 1
			while s and s[-1][0] >= A[i]:
				count += s.pop()[1]
			left[i] = count
			s.append((A[i], count))
		s = []
		for i in range(n - 1, -1, -1):
			count = 1
			while s and s[-1][0] > A[i]:
				count += s.pop()[1]
			right[i] = count
			s.append((A[i], count))
		print(left)
		print(right)
		s = 0
		for i in range(n):
			s += left[i] * right[i] * A[i]
		return s % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A):
		(n, mod) = (len(A), 10 ** 9 + 7)
		(left, right, s1, s2) = ([0] * n, [0] * n, [], [])
		for i in range(n):
			count = 1
			while s1 and s1[-1][0] > A[i]:
				count += s1.pop()[1]
			left[i] = count
			s1.append([A[i], count])
		for i in range(n)[::-1]:
			count = 1
			while s2 and s2[-1][0] >= A[i]:
				count += s2.pop()[1]
			right[i] = count
			s2.append([A[i], count])
		return sum((a * l * r for (a, l, r) in zip(A, left, right))) % mod


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		m = 10 ** 9 + 7
		prev_stack = []
		next_stack = []
		prev_smaller = {}
		next_smaller = {}
		for i in range(len(A)):
			while len(next_stack) > 0 and next_stack[-1][0] >= A[i]:
				(elem, idx) = next_stack.pop()
				next_smaller[idx] = i
			next_stack.append([A[i], i])
		while len(next_stack) != 0:
			(elem, idx) = next_stack.pop()
			next_smaller[idx] = len(A)
		for i in range(len(A) - 1, -1, -1):
			while len(prev_stack) > 0 and prev_stack[-1][0] > A[i]:
				(elem, idx) = prev_stack.pop()
				prev_smaller[idx] = i
			prev_stack.append([A[i], i])
		while len(prev_stack) != 0:
			(elem, idx) = prev_stack.pop()
			prev_smaller[idx] = -1
		result = 0
		for i in range(len(A)):
			left_count = i - prev_smaller[i] - 1
			right_count = next_smaller[i] - i - 1
			num_occurrences = (left_count + 1) * (right_count + 1)
			result = (result + num_occurrences * A[i]) % m
		return result


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		mod = 10 ** 9 + 7
		A = [0] + A + [0]
		n = len(A)
		stack = []
		res = 0
		for i in range(n):
			while stack and A[stack[-1]] > A[i]:
				curr = stack.pop(-1)
				left = stack[-1]
				right = i
				res += A[curr] * (curr - left) * (right - curr)
			stack.append(i)
		res %= 10 ** 9 + 7
		return res


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		n = len(A)
		stack = []
		l_count = []
		for i in range(n):
			while stack and A[stack[-1]] > A[i]:
				stack.pop()
			l_c = 0
			if stack:
				l_c = stack[-1] + 1
			stack.append(i)
			l_count.append(l_c)
		stack = []
		r_count = []
		for i in range(n):
			while stack and A[stack[-1]] >= A[n - i - 1]:
				stack.pop()
			r_c = n - 1
			if stack:
				r_c = stack[-1] - 1
			stack.append(n - i - 1)
			r_count.append(r_c)
		r_count = r_count[::-1]
		t = 0
		print(l_count)
		print(r_count)
		for i in range(n):
			l = l_count[i]
			r = r_count[i]
			t += (i - l + 1) * (r - i + 1) * A[i]
		return t % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		mod = 10 ** 9 + 7
		stack = []
		ans = dot = 0
		for (idx, val) in enumerate(A):
			count = 1
			while stack and stack[-1][0] >= val:
				(x, c) = stack.pop()
				count += c
				dot -= x * c
			stack.append((val, count))
			dot += val * count
			ans += dot
		return ans % mod


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		N = len(A)
		stack = []
		res = 0
		instack = 0
		for i in range(N):
			tmp = 1
			while stack and stack[-1][0] >= A[i]:
				(x, cnt) = stack.pop()
				tmp += cnt
				instack -= x * cnt
			stack.append((A[i], tmp))
			instack += A[i] * tmp
			res += instack
		return res % (10 ** 9 + 7)


from collections import deque

class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		stack = deque()
		left = [0] * len(A)
		right = [len(A)] * len(A)
		mod = 10 ** 9 + 7
		for i in range(len(A)):
			while stack and A[stack[-1]] > A[i]:
				right[stack[-1]] = i
				stack.pop()
			left[i] = stack[-1] if stack else -1
			stack.append(i)
		res = 0
		for i in range(len(A)):
			res += A[i] * (i - left[i]) * (right[i] - i)
		return res % mod


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		length = len(A)
		left = [-1 for _ in range(length)]
		right = [length for _ in range(length)]
		(stack, res, N) = ([], 0, 10 ** 9 + 7)
		for i in range(length):
			while stack and A[stack[-1]] > A[i]:
				right[stack.pop()] = i
			if stack:
				left[i] = stack[-1]
			stack.append(i)
		for i in range(length):
			res += (i - left[i]) * (right[i] - i) * A[i]
		return res % N


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		mod = 10 ** 9 + 7
		(left, right) = self.findFirstSmaller(A)
		ans = 0
		for i in range(len(A)):
			ans += A[i] % mod * ((right[i] - 1 - i + 1) * (i - (left[i] + 1) + 1)) % mod
		return ans % mod

	def findFirstSmaller(self, A):
		(left, right) = ([-1] * len(A), [len(A)] * len(A))
		stack = []
		for (i, n) in enumerate(A):
			while stack and stack[-1][0] > n:
				right[stack.pop()[1]] = i
			if stack:
				left[i] = stack[-1][1]
			stack.append((n, i))
		return (left, right)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		stack = [-1]
		A.append(float('-inf'))
		res = 0
		for (i, num) in enumerate(A):
			while A[stack[-1]] > num:
				center = stack.pop()
				res += (i - center) * (center - stack[-1]) * A[center]
			stack.append(i)
		return res % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		(n, mod) = (len(A), 10 ** 9 + 7)
		s = []
		left = [i + 1 for i in range(n)]
		right = [n - i for i in range(n)]
		res = 0
		for i in range(n):
			while s and A[s[-1]] > A[i]:
				k = s.pop()
				right[k] = i - k
			left[i] = i + 1 if not s else i - s[-1]
			s.append(i)
		print(right)
		print(left)
		return sum((a * i * j for (a, i, j) in zip(A, left, right))) % mod


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		left = []
		right = []
		stack = []
		for i in range(len(A)):
			left.append(i + 1)
			right.append(len(A) - i)
		for i in range(len(A)):
			while stack and A[i] < A[stack[-1]]:
				poppedIdx = stack.pop()
				right[poppedIdx] = i - poppedIdx
			if stack:
				left[i] = i - stack[-1]
			else:
				left[i] = i + 1
			stack.append(i)
		ans = 0
		for i in range(len(A)):
			ans = (ans + left[i] * right[i] * A[i]) % 1000000007
		return ans


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		N = len(A)
		stack = []
		(left, right) = ([None] * N, [None] * N)
		for i in range(N):
			while stack and A[i] <= A[stack[-1]]:
				stack.pop()
			left[i] = stack[-1] if stack else -1
			stack.append(i)
		stack.clear()
		for i in range(N - 1, -1, -1):
			while stack and A[i] < A[stack[-1]]:
				stack.pop()
			right[i] = stack[-1] if stack else N
			stack.append(i)
		count = 0
		for i in range(N):
			count += (i - left[i]) * (right[i] - i) * A[i]
		return count % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		MOD = 10 ** 9 + 7
		n = len(A)
		stack = []
		left = [None] * n
		for i in range(n):
			while stack and A[i] <= A[stack[-1]]:
				stack.pop()
			if stack:
				left[i] = stack[-1]
			else:
				left[i] = -1
			stack.append(i)
		stack = []
		right = [n] * n
		for i in range(n):
			while stack and A[i] <= A[stack[-1]]:
				right[stack.pop()] = i
			stack.append(i)
		res = 0
		for i in range(n):
			res += (i - left[i]) * (right[i] - i) * A[i]
		return res % MOD


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		N = len(A)
		if N == 0:
			return 0
		mod = 10 ** 9 + 7
		(stack, left, right) = ([], [0] * N, [0] * N)
		for i in range(N):
			count = 1
			while stack and stack[-1][0] > A[i]:
				count += stack.pop()[1]
			left[i] = count
			stack.append((A[i], count))
		stack.clear()
		for i in range(N - 1, -1, -1):
			count = 1
			while stack and stack[-1][0] >= A[i]:
				count += stack.pop()[1]
			right[i] = count
			stack.append((A[i], count))
		return sum([l * r * v for (l, r, v) in zip(left, right, A)]) % mod


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		mod = 10 ** 9 + 7
		left = [-1] * len(A)
		right = [len(A)] * len(A)
		stack = [0]
		for i in range(1, len(A)):
			if A[i] > A[stack[-1]]:
				left[i] = stack[-1]
			else:
				while stack and A[i] <= A[stack[-1]]:
					stack.pop()
				if not stack:
					left[i] = -1
				else:
					left[i] = stack[-1]
			stack.append(i)
		stack = [len(A) - 1]
		for i in range(len(A) - 2, -1, -1):
			if A[i] > A[stack[-1]]:
				right[i] = stack[-1]
			else:
				while stack and A[i] < A[stack[-1]]:
					stack.pop()
				if not stack:
					right[i] = len(A)
				else:
					right[i] = stack[-1]
			stack.append(i)
		res = 0
		for i in range(len(A)):
			res += A[i] * (i - left[i]) * (right[i] - i)
		return res % mod


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		res = 0
		stack = []
		A = [float('-inf')] + A + [float('-inf')]
		for (i, n) in enumerate(A):
			while stack and A[stack[-1]] > n:
				cur = stack.pop()
				res += A[cur] * (cur - stack[-1]) * (i - cur)
			stack.append(i)
		return res % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		N = len(A)
		if N == 0:
			return 0
		mod = 10 ** 9 + 7
		(stackLeft, stackRight, left, right) = ([], [], [0] * N, [0] * N)
		for L in range(N):
			while stackLeft and A[stackLeft[-1]] > A[L]:
				stackLeft.pop()
			left[L] = L - (stackLeft[-1] if stackLeft else -1)
			stackLeft.append(L)
			R = N - L - 1
			while stackRight and A[stackRight[-1]] >= A[R]:
				stackRight.pop()
			right[R] = stackRight[-1] - R if stackRight else N - R
			stackRight.append(R)
		return sum([l * r * v for (l, r, v) in zip(left, right, A)]) % mod


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		n = len(A)
		(left, right) = ([i + 1 for i in range(n)], [n - i for i in range(n)])
		(stackp, stackn) = ([], [])
		for (i, num) in enumerate(A):
			while stackp and num < A[stackp[-1]]:
				stackp.pop()
			if stackp:
				left[i] = i - stackp[-1]
			stackp.append(i)
			while stackn and num < A[stackn[-1]]:
				curr = stackn.pop()
				right[curr] = i - curr
			stackn.append(i)
		res = 0
		mod = 10 ** 9 + 7
		for (i, num) in enumerate(A):
			res = (res + left[i] * right[i] * num) % mod
		return res


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		ple_stack = []
		left = [-1] * len(A)
		for i in range(len(A)):
			while ple_stack and A[i] < A[ple_stack[-1]]:
				ple_stack.pop()
			left[i] = ple_stack[-1] if ple_stack else -1
			ple_stack.append(i)
		for i in range(len(A)):
			left[i] = i - left[i]
		nle_stack = []
		right = [-1] * len(A)
		for j in reversed(range(len(A))):
			while nle_stack and A[j] <= A[nle_stack[-1]]:
				nle_stack.pop()
			right[j] = nle_stack[-1] if nle_stack else len(A)
			nle_stack.append(j)
		for j in range(len(A)):
			right[j] = right[j] - j
		return sum([x * y * z for (x, y, z) in zip(left, right, A)]) % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		mod = 10 ** 9 + 7
		(left, right) = (self.PLE(A), self.NLE(A))
		return sum((a * i * j for (a, i, j) in zip(A, left, right))) % mod

	def PLE(self, A):
		n = len(A)
		left = [-1] * n
		stack = []
		for i in range(n):
			while stack and A[stack[-1]] > A[i]:
				stack.pop()
			if stack:
				left[i] = stack[-1]
			stack.append(i)
		for i in range(n):
			left[i] = i + 1 if left[i] == -1 else i - left[i]
		return left

	def NLE(self, A):
		n = len(A)
		right = [-1] * n
		stack = []
		for i in range(n):
			while stack and A[stack[-1]] > A[i]:
				right[stack.pop()] = i
			stack.append(i)
		for i in range(n):
			right[i] = n - i if right[i] == -1 else right[i] - i
		return right


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		MOD = 10 ** 9 + 7
		cl = []
		stack = []
		for i in range(len(A)):
			while stack and A[stack[-1]] > A[i]:
				stack.pop()
			if not stack:
				l = i + 1
			else:
				l = i - stack[-1]
			cl.append(l)
			stack.append(i)
		cr = []
		stack = []
		for i in range(len(A) - 1, -1, -1):
			while stack and A[stack[-1]] >= A[i]:
				stack.pop()
			if not stack:
				r = len(A) - i
			else:
				r = stack[-1] - i
			stack.append(i)
			cr.append(r)
		cr = cr[::-1]
		tot = 0
		for i in range(len(A)):
			tot += A[i] * cl[i] * cr[i]
			tot %= 10 ** 9 + 7
		return tot


from queue import deque
from collections import defaultdict

class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		A = [float('-inf')] + A + [float('-inf')]
		left = deque()
		left.append(0)
		right = deque()
		right.appendleft(len(A) - 1)
		left_b = defaultdict(int)
		right_b = defaultdict(int)
		for i in range(1, len(A) - 1):
			while left and A[left[-1]] > A[i]:
				left.pop()
			left_b[i] = left[-1] + 1
			left.append(i)
		for i in reversed(range(1, len(A) - 1)):
			while right and A[right[0]] >= A[i]:
				right.popleft()
			right_b[i] = right[0] - 1
			right.appendleft(i)
		res = 0
		for i in range(1, len(A) - 1):
			res += (i - left_b[i] + 1) * (right_b[i] - i + 1) * A[i]
		return res % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		l = len(A)
		left = [0 for _ in range(l)]
		right = [0 for _ in range(l)]
		s = []
		res = 0
		for i in range(l):
			if s:
				if A[i] > A[s[-1]]:
					s.append(i)
				else:
					while s and A[i] < A[s[-1]]:
						s.pop()
					if s == []:
						left[i] = i
					else:
						left[i] = i - s[-1] - 1
					s.append(i)
			else:
				s.append(i)
		A = A[::-1]
		s = []
		for i in range(l):
			if s:
				if A[i] > A[s[-1]]:
					s.append(i)
				else:
					while s and A[i] <= A[s[-1]]:
						s.pop()
					if s == []:
						right[i] = i
					else:
						right[i] = i - s[-1] - 1
					s.append(i)
			else:
				s.append(i)
		for i in range(l):
			res += A[l - 1 - i] * (left[i] + 1) * (right[l - 1 - i] + 1)
		return res % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		N = len(A)
		lefts = []
		st = []
		for (i, num) in enumerate(A):
			cnt = 1
			while st and st[-1][0] > num:
				(prev_num, prev_cnt) = st.pop()
				cnt += prev_cnt
			st.append([num, cnt])
			lefts.append(cnt)
		rights = []
		st = []
		for (i, num) in reversed(list(enumerate(A))):
			cnt = 1
			while st and st[-1][0] >= num:
				(prev_num, prev_cnt) = st.pop()
				cnt += prev_cnt
			st.append([num, cnt])
			rights.append(cnt)
		ans = 0
		for (lc, num, rc) in zip(lefts, A, rights[::-1]):
			ans += lc * num * rc
		return ans % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		s = []
		n = len(A)
		left = [1] * n
		right = [1] * n
		for i in range(n):
			while len(s) > 0 and s[-1][0] >= A[i]:
				(val, cnt) = s.pop()
				left[i] += cnt
			s.append([A[i], left[i]])
		s = []
		for i in range(n - 1, -1, -1):
			while len(s) > 0 and s[-1][0] > A[i]:
				(val, cnt) = s.pop()
				right[i] += cnt
			s.append((A[i], right[i]))
		total = 0
		for (a, l, r) in zip(A, left, right):
			total += a * l * r
		return total % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		mod = 10 ** 9 + 7
		curr_sum = 0
		last_sum = 0
		stack = []
		for a in A:
			cnt = 1
			last_sum = (last_sum + a) % mod
			while stack and a < stack[-1][0]:
				(b, c) = stack.pop()
				cnt = (cnt + c) % mod
				last_sum = (last_sum - (b - a) * c) % mod
			if stack and stack[-1][0] == a:
				stack[-1][1] = (stack[-1][1] + cnt) % mod
			else:
				stack.append([a, cnt])
			curr_sum = (curr_sum + last_sum) % mod
		return curr_sum


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		result = 0
		tempDq = []
		A = [0] + A + [0]
		for idx in range(len(A)):
			while tempDq and A[tempDq[-1]] > A[idx]:
				prevIdx = tempDq.pop()
				lastIdx = tempDq[-1]
				result += A[prevIdx] * (prevIdx - lastIdx) * (idx - prevIdx)
			tempDq.append(idx)
		return result % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		A = [0] + A
		stack = [0]
		result = [0] * len(A)
		for i in range(len(A)):
			while A[stack[-1]] > A[i]:
				stack.pop()
			j = stack[-1]
			result[i] = result[j] + (i - j) * A[i]
			stack.append(i)
		return sum(result) % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		s = []
		left = [None] * len(A)
		for i in range(len(A)):
			count = 1
			while len(s) > 0 and A[i] <= s[-1][0]:
				count += s.pop()[1]
			s.append((A[i], count))
			left[i] = count
		s = []
		right = [None] * len(A)
		for i in range(len(A) - 1, -1, -1):
			count = 1
			while len(s) > 0 and A[i] < s[-1][0]:
				count += s.pop()[1]
			s.append((A[i], count))
			right[i] = count
		_sum = 0
		for i in range(len(A)):
			_sum = _sum + A[i] * (left[i] * right[i])
		return int(_sum % (1000000000.0 + 7))


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		ans = 0
		st = []
		n = len(A)
		left = [0] * n
		right = [0] * n
		mod = pow(10, 9) + 7
		for i in range(len(A)):
			c = 1
			while st and st[-1][0] > A[i]:
				c += st.pop()[1]
			left[i] = c
			st.append((A[i], c))
		st = []
		for i in list(range(len(A)))[::-1]:
			c = 1
			while st and st[-1][0] >= A[i]:
				c += st.pop()[1]
			right[i] = c
			st.append((A[i], c))
		ans = 0
		m = pow(10, 9) + 7
		print(left)
		print(right)
		for (a, b, c) in zip(A, left, right):
			ans += a * b * c
			ans = ans % m
		return ans


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		N = len(A)
		if N == 0:
			return 0
		mod = 10 ** 9 + 7
		res = 0
		s = []
		A = [0] + A + [0]
		for (i, x) in enumerate(A):
			while s and A[s[-1]] > x:
				j = s.pop()
				k = s[-1]
				res += A[j] * (i - j) * (j - k)
			s.append(i)
		return res % mod


class Solution:

	def next_smallest(self, A):
		inds = [-1] * len(A)
		stack = []
		for (i, val) in enumerate(A):
			while len(stack) > 0 and A[stack[-1]] > val:
				inds[stack[-1]] = i
				stack.pop()
			stack += [i]
		return inds

	def last_smallest(self, A):
		inds = [-1] * len(A)
		stack = []
		for (i, val) in reversed(list(enumerate(A))):
			while len(stack) > 0 and A[stack[-1]] >= val:
				inds[stack[-1]] = i
				stack.pop()
			stack += [i]
		return inds

	def sumSubarrayMins(self, A):
		left = self.last_smallest(A)
		right = self.next_smallest(A)
		tot = 0
		n = len(A)
		for (i, val) in enumerate(A):
			p = left[i]
			q = right[i]
			a = i - p
			b = q - i
			if p == -1:
				a = i + 1
			if q == -1:
				b = n - i
			nseqs = a * b
			tot += nseqs * val
		return tot % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		(s1, s2) = ([], [])
		left = [None] * len(A)
		right = [None] * len(A)
		for i in range(len(A)):
			count1 = 1
			while len(s1) > 0 and A[i] <= s1[-1][0]:
				count1 = count1 + s1.pop()[1]
			s1.append((A[i], count1))
			left[i] = count1
			j = len(A) - 1 - i
			count2 = 1
			while len(s2) > 0 and A[j] < s2[-1][0]:
				count2 += s2.pop()[1]
			s2.append((A[j], count2))
			right[j] = count2
		_sum = 0
		for i in range(len(A)):
			_sum = _sum + A[i] * (left[i] * right[i])
		return int(_sum % (1000000000.0 + 7))


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		(l, r) = ([None] * len(A), [None] * len(A))
		(s1, s2) = ([], [])
		for i in range(len(A)):
			c = 1
			while s1 and s1[-1][0] >= A[i]:
				c += s1[-1][1]
				s1.pop(-1)
			s1.append([A[i], c])
			l[i] = c
		for i in range(len(A) - 1, -1, -1):
			c = 1
			while s2 and s2[-1][0] > A[i]:
				c += s2[-1][1]
				s2.pop(-1)
			s2.append([A[i], c])
			r[i] = c
		result = 0
		for i in range(len(A)):
			result += A[i] * l[i] * r[i]
		return result % (10 ** 9 + 7)


MOD = 1000000007

class Solution:

	def sumSubarrayMins(self, A):
		A = [0] + A + [0]
		stack = []
		res = 0
		for right in range(len(A)):
			while stack and A[stack[-1]] > A[right]:
				mid = stack.pop()
				left = stack[-1]
				res += A[mid] * (mid - left) * (right - mid)
				res %= MOD
			stack.append(right)
		return res


class Solution:

	def previousLessNumber(self, A: List[int]) -> List[int]:
		plmStack = []
		plmResult = [-1] * len(A)
		i = 0
		while i < len(A):
			while len(plmStack) > 0 and A[plmStack[-1]] >= A[i]:
				plmStack.pop()
			plmResult[i] = -1 if len(plmStack) == 0 else plmStack[-1]
			plmStack.append(i)
			i += 1
		return plmResult

	def nextLessNumber(self, A: List[int]) -> List[int]:
		nlmStack = []
		nlmResult = [-1] * len(A)
		i = len(A) - 1
		while i >= 0:
			while len(nlmStack) > 0 and A[nlmStack[-1]] > A[i]:
				nlmStack.pop()
			nlmResult[i] = -1 if len(nlmStack) == 0 else nlmStack[-1]
			nlmStack.append(i)
			i -= 1
		return nlmResult

	def sumSubarrayMins(self, A: List[int]) -> int:
		plmResult = self.previousLessNumber(A)
		nlmResult = self.nextLessNumber(A)
		print(plmResult)
		print(nlmResult)
		sum = 0
		for i in range(len(A)):
			leftDist = 0
			if plmResult[i] == -1:
				leftDist = i + 1
			else:
				leftDist = i - plmResult[i]
			rightDist = 0
			if nlmResult[i] == -1:
				rightDist = len(A) - i
			else:
				rightDist = nlmResult[i] - i
			sum = (sum + A[i] * leftDist * rightDist) % (10 ** 9 + 7)
		return sum


import numpy as np

class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		stack = []
		(left, right) = ([], [])
		for i in range(len(A)):
			cnt = 1
			while stack and A[i] <= stack[-1][0]:
				cnt += stack[-1][1]
				stack.pop()
			stack.append([A[i], cnt])
			left.append(cnt)
		stack = []
		for i in range(len(A) - 1, -1, -1):
			cnt = 1
			while stack and A[i] < stack[-1][0]:
				cnt += stack[-1][1]
				stack.pop()
			stack.append([A[i], cnt])
			right.append(cnt)
		right = right[::-1]
		res = 0
		for i in range(len(A)):
			res += A[i] * left[i] * right[i]
		return res % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		MOD = 10 ** 9 + 7
		result = 0
		stack = []
		my_dict = {}
		for i in range(0, len(A)):
			if stack == []:
				stack.append((i, A[i]))
				my_dict[i, A[i]] = [0]
			elif A[i] >= stack[-1][1]:
				stack.append((i, A[i]))
				my_dict[i, A[i]] = [0]
			else:
				while stack != [] and A[i] < stack[-1][1]:
					temp = stack.pop()
					my_dict[temp].append(i - temp[0] - 1)
				if stack == []:
					stack.append((i, A[i]))
					my_dict[i, A[i]] = [i]
				else:
					stack.append((i, A[i]))
					my_dict[i, A[i]] = [i - 1 - stack[-2][0]]
		for key in my_dict:
			if len(my_dict[key]) == 1:
				my_dict[key].append(len(A) - 1 - key[0])
			result += key[1] * (my_dict[key][0] + 1) * (my_dict[key][1] + 1)
		return result % MOD


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		stack = []
		bound = [[0, 0] for x in range(0, len(A))]
		for i in range(0, len(A)):
			while 0 < len(stack) and A[i] <= stack[-1][0]:
				bound[stack[-1][1]][1] = i
				stack.pop()
			stack.append((A[i], i))
		while 0 < len(stack):
			bound[stack[-1][1]][1] = len(A)
			stack.pop()
		index = len(A) - 1
		while 0 <= index:
			while 0 < len(stack) and A[index] < stack[-1][0]:
				bound[stack[-1][1]][0] = index
				stack.pop()
			stack.append((A[index], index))
			index -= 1
		while 0 < len(stack):
			bound[stack[-1][1]][0] = -1
			stack.pop()
		sum = 0
		for i in range(0, len(bound)):
			sum += A[i] * (i - bound[i][0]) * (bound[i][1] - i)
			sum %= 10 ** 9 + 7
		return sum


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		n = len(A)
		l_large = [0] * n
		l_stack = [(A[0], 0)]
		r_large = [0] * n
		r_stack = [(A[n - 1], n - 1)]
		for i in range(1, n):
			while l_stack and A[i] < l_stack[-1][0]:
				(_, idx) = l_stack.pop()
				l_large[i] = max(l_large[i], i - idx + l_large[idx])
			else:
				l_stack.append((A[i], i))
			while r_stack and A[n - i - 1] <= r_stack[-1][0]:
				(_, idx) = r_stack.pop()
				r_large[n - i - 1] = max(r_large[n - i - 1], idx - (n - i - 1) + r_large[idx])
			else:
				r_stack.append((A[n - i - 1], n - i - 1))
		return sum(((1 + l_large[i] + r_large[i] + l_large[i] * r_large[i]) * A[i] for i in range(n))) % int(1000000007)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		(res, curr_sum, min_arr) = (0, 0, [(float('-inf'), -1)])
		for (i, a) in enumerate(A):
			while min_arr and a < min_arr[-1][0]:
				(b, j) = min_arr.pop()
				curr_sum -= b * (j - min_arr[-1][1])
			curr_sum += a * (i - min_arr[-1][1])
			min_arr.append((a, i))
			res += curr_sum
		return res % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		mod = 10 ** 9 + 7
		A = [0] + A + [0]
		q = [-1]
		res = 0
		cur = 0
		for (i, x) in enumerate(A):
			while q and A[q[-1]] > x:
				cur -= A[q[-1]] * (q[-1] - q[-2])
				q.pop()
			res += x * (i - q[-1]) + cur
			cur += x * (i - q[-1])
			q.append(i)
		return res % mod


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		left = [1] * len(A)
		right = [1] * len(A)
		stack = []
		for (i, v) in enumerate(A):
			if i == 0:
				stack.append(i)
				left[i] = 1
			else:
				count = 1
				while stack and A[stack[-1]] > v:
					count += left[stack.pop()]
				left[i] = count
				stack.append(i)
		stack = []
		for i in range(len(A) - 1, -1, -1):
			count = 1
			while stack and A[stack[-1]] >= A[i]:
				count += right[stack.pop()]
			right[i] = count
			stack.append(i)
		sum = 0
		for i in range(len(A)):
			sum = sum + left[i] * right[i] * A[i]
		return sum % 1000000007


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		A = [float('-inf')] + A + [float('-inf')]
		stack = [0]
		res = 0
		for i in range(1, len(A)):
			while A[i] < A[stack[-1]]:
				j = stack.pop()
				k = stack[-1]
				res += A[j] * (i - j) * (j - k)
				res %= 10 ** 9 + 7
			stack.append(i)
		return res


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		stack = []
		mult = 0
		ans = 0
		for curr_val in A:
			curr_cnt = 1
			while stack and stack[-1][0] >= curr_val:
				(val_p, cnt_p) = stack.pop()
				curr_cnt += cnt_p
				mult -= val_p * cnt_p
			stack.append((curr_val, curr_cnt))
			mult += curr_val * curr_cnt
			ans += mult
		return ans % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		n = len(A)
		left = self.first_left_smallest(A)
		right = self.first_right_smallest(A)
		count = 0
		MOD = 10 ** 9 + 7
		for i in range(n):
			l = left[i] if left[i] != None else -1
			r = right[i] if right[i] != None else n
			n1 = i - l - 1
			n2 = r - i - 1
			num_of_sub = (n1 + 1) * (n2 + 1)
			print((i, num_of_sub))
			count += A[i] * num_of_sub
		return count % MOD

	def first_left_smallest(self, A):
		n = len(A)
		stack = []
		res = [None] * n
		for i in range(n - 1, -1, -1):
			while stack and A[i] <= A[stack[-1]]:
				j = stack.pop()
				res[j] = i
			stack.append(i)
		return res

	def first_right_smallest(self, A):
		n = len(A)
		stack = []
		res = [None] * n
		for i in range(n):
			while stack and A[i] < A[stack[-1]]:
				j = stack.pop()
				res[j] = i
			stack.append(i)
		return res

	def brute_force(self, A):
		n = len(A)
		s = 0
		for i in range(n):
			smallest = float('inf')
			for j in range(i, n):
				smallest = min(smallest, A[j])
				s += smallest
		return s % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		n = len(A)
		pre_stack = []
		pre_val = [-1] * n
		for (i, a) in enumerate(A):
			while pre_stack and A[pre_stack[-1]] >= a:
				pre_stack.pop()
			if pre_stack:
				pre_val[i] = pre_stack[-1] + 1
			else:
				pre_val[i] = 0
			pre_stack.append(i)
		post_stack = []
		post_val = [-1] * n
		for i in range(n - 1, -1, -1):
			while post_stack and A[post_stack[-1]] > A[i]:
				post_stack.pop()
			if post_stack:
				post_val[i] = post_stack[-1] - 1
			else:
				post_val[i] = n - 1
			post_stack.append(i)
		ans = 0
		mod_cst = 10 ** 9 + 7
		for i in range(n):
			ans += (i - pre_val[i] + 1) * (post_val[i] - i + 1) * A[i]
			ans %= mod_cst
		return ans


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		(res, stack, MOD) = (0, [], 10 ** 9 + 7)
		for (i, x) in enumerate(A):
			while stack and A[stack[-1]] >= x:
				idx = stack.pop()
				left = stack[-1] if stack else -1
				res += A[idx] * (idx - left) * (i - idx) % MOD
			stack.append(i)
		while stack:
			idx = stack.pop()
			left = stack[-1] if stack else -1
			res += A[idx] * (idx - left) * (len(A) - idx) % MOD
		return res % MOD


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		dp = []
		dp_forward = [0] * len(A)
		dp_backward = [0] * len(A)
		for i in range(len(A)):
			while dp and A[i] < dp[-1][0]:
				dp_forward[i] += dp.pop()[1] + 1
			dp.append([A[i], dp_forward[i]])
		print(dp_forward)
		dp = []
		for i in range(len(A) - 1, -1, -1):
			while dp and A[i] <= dp[-1][0]:
				dp_backward[i] += dp.pop()[1] + 1
			dp.append([A[i], dp_backward[i]])
		print(dp_backward)
		result = 0
		for i in range(len(A)):
			result += A[i] * (dp_forward[i] + 1) * (dp_backward[i] + 1)
		return result % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		n = len(A)
		left = [0] * n
		right = [0] * n
		s1 = []
		s2 = []
		mod = 10 ** 9 + 7
		for i in range(n):
			cnt = 1
			while s1 and s1[-1][0] > A[i]:
				cnt += s1.pop()[1]
			s1.append((A[i], cnt))
			left[i] = cnt
		for i in range(n - 1, -1, -1):
			cnt = 1
			while s2 and s2[-1][0] >= A[i]:
				cnt += s2.pop()[1]
			s2.append((A[i], cnt))
			right[i] = cnt
		return sum((A[i] * left[i] * right[i] for i in range(n))) % mod


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:

		def right_boundry(A, dupl):
			res = [0] * len(A)
			A.append(-math.inf)
			stack = []
			for i in range(len(A)):
				if dupl:
					while stack and A[stack[-1]] > A[i]:
						j = stack.pop()
						res[j] = i - j
				else:
					while stack and A[stack[-1]] >= A[i]:
						j = stack.pop()
						res[j] = i - j
				stack.append(i)
			A.pop()
			return res
		right = right_boundry(A, False)
		left = right_boundry(A[::-1], True)[::-1]
		ans = sum([right[i] * left[i] * A[i] for i in range(len(A))])
		return ans % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		larr = [-1] * len(A)
		rarr = [-1] * len(A)
		for i in range(len(A)):
			lefti = i - 1
			while lefti > -1 and A[lefti] > A[i]:
				lefti = larr[lefti] - 1
			larr[i] = lefti + 1
		for i in range(len(A) - 1, -1, -1):
			righti = i + 1
			while righti < len(A) and A[righti] >= A[i]:
				righti = rarr[righti] + 1
			rarr[i] = righti - 1
		count = 0
		for i in range(len(A)):
			(r, l) = (rarr[i] - i, i - larr[i])
			count += (1 + l + r + l * r) * A[i]
		return count % (10 ** 9 + 7)


class Solution:

	def sumSubarrayMins(self, A: List[int]) -> int:
		(left, right) = ([], [])
		stack = []
		for i in range(len(A)):
			count = 1
			while stack and stack[-1][0] > A[i]:
				count += stack.pop()[1]
			stack.append([A[i], count])
			left.append(count)
		stack = []
		for i in reversed(range(len(A))):
			count = 1
			while stack and stack[-1][0] >= A[i]:
				count += stack.pop()[1]
			stack.append([A[i], count])
			right.append(count)
		right = right[::-1]
		res = 0
		for i in range(len(A)):
			res += left[i] * right[i] * A[i]
		return res % (10 ** 9 + 7)