Given an array A[] with N elements , you need to find the sum all sub arrays of array A. Since the sum could be very large print the sum modulo (10^{9}+7).
Example 1:
Input:
N = 3
A[] = {1, 2, 3}
Output: 20
Explanation:
All subarrays are [1], [2], [3],
[1,2], [2,3], [1,2,3].
Thus total sum is 20.
 
Example 2:
Input:
N = 2
A[] = {1, 3}
Output: 8
Your Task:  
You don't need to read input or print anything. Your task is to complete the function subarraySum() which takes the array A[] and its size N as inputs and returns the sum.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints :
1 ≤ N ≤ 10^{5}
1 ≤ A[] ≤ 10^{9}

Difficulty: MEDIUM
Tags: Number theory

Data structures

Mathematics
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def subarraySum(self, a, n):

        # code here 

Solutions:
class Solution:

	def subarraySum(self, a, n):
		s = 0
		for i in range(n):
			s += a[i] * (i + 1) * (n - i)
		return s % 1000000007


class Solution:

	def subarraySum(self, a, n):
		MOD = 10 ** 9 + 7
		ans = 0
		for i in range(n):
			ans += a[i] * (i + 1) * (n - i)
			ans %= MOD
		return ans


class Solution:

	def subarraySum(self, a, n):
		dp = [0] * n
		dp[0] = a[0]
		mod = int(1000000000.0 + 7)
		s = a[0]
		for i in range(1, n):
			dp[i] = dp[i - 1] + a[i] * (i + 1)
			dp[i] = dp[i]
			s += dp[i]
		return s % mod


class Solution:

	def subarraySum(self, arr, n):
		result = 0
		for i in range(0, n):
			result += arr[i] * (i + 1) * (n - i) % 1000000007
		return result % 1000000007


class Solution:

	def subarraySum(self, a, n):
		ans = 0
		MOD = 1000000007
		for i in range(n):
			ans += (n + i * (n - 1 - i)) * a[i]
		return ans % MOD


class Solution:

	def subarraySum(self, a, n):
		c = 0
		for i in range(n):
			if i == 0 or i == n - 1:
				c += a[i] * n
			else:
				c += a[i] * ((n - i) * (i + 1))
		return c % 1000000007


class Solution:

	def subarraySum(self, a, n):
		(s, m) = (0, 10 ** 9 + 7)
		for i in range(n):
			s += (n - i) * a[i] * (i + 1) % m
		return s % m


from math import factorial

class Solution:

	def subarraySum(self, a, n):
		mod = 10 ** 9 + 7
		summa = 0
		for i in range(n):
			summa += a[i] * (n - i) * (1 + i)
			summa = summa % mod
		return summa


def mathematical(arr):
	n = len(arr)
	total = 0
	for i in range(n):
		total += (n - i) * (i + 1) * arr[i]
	return total

class Solution:

	def subarraySum(self, a, n):
		return mathematical(a) % (10 ** 9 + 7)


class Solution:

	def subarraySum(self, arr, n):
		m = 10 ** 9 + 7
		Sum = 0
		for i in range(n):
			Sum += arr[i] * (n - i) * (i + 1)
		return Sum % m


class Solution:

	def subarraySum(self, a, n):
		summation = 0
		dec = 0
		front = 0
		for i in range(n):
			value = front + (n - i) + dec
			front = value
			dec -= 1
			summation += value * a[i]
		return summation % (10 ** 9 + 7)


class Solution:

	def subarraySum(self, a, n):
		su = 0
		mod = 10 ** 9 + 7
		for i in range(0, n):
			su += a[i] * (i + 1) * (n - i)
		return su % mod


MAX_RES = 1000000007

class Solution:

	@staticmethod
	def subarraySum(a, n):
		sum = 0
		for x in range(0, n):
			sum += a[x] * (x + 1) * (n - x)
		return sum % MAX_RES


P = 10 ** 9 + 7

class Solution:

	def subarraySum(self, arr, n):
		total = 0
		csum = 0
		for i in range(n):
			csum = (csum + arr[i] * (i + 1)) % P
			total = (total + csum) % P
		return total


class Solution:

	def subarraySum(self, a, n):
		sum = 0
		p = 1000000007
		for i in range(0, n):
			sum = (sum + (i + 1) * a[i] % p * (n - i) % p) % p
		return sum


class Solution:

	def subarraySum(self, a, n):
		s = 0
		c = (n + 1) // 2
		b = a[:c]
		d = a[c:]
		d = d[::-1]
		e = 1
		f = n
		for i in b:
			s += e * f * i
			f -= 1
			e += 1
		e = 1
		f = n
		for i in d:
			s += e * f * i
			f -= 1
			e += 1
		return s % 1000000007


class Solution:

	def subarraySum(self, a, n):
		total = 0
		for i in range(0, n):
			total += a[i] * (n - i) * (i + 1)
		return total % (10 ** 9 + 7)

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.subarraySum(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def subarraySum(self, a, n):
		sum = 0
		p = 1000000007
		for i in range(0, n):
			sum = (sum + (i + 1) * a[i] % p * (n - i) % p) % p
		return sum

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.subarraySum(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def __init__(self):
		self.M = 10 ** 9 + 7

	def subarraySum(self, A, n):
		total = 0
		for (i, num) in enumerate(A):
			count = (i + 1) * (n - i)
			total = (total + count * num) % self.M
		return total


class Solution:

	def subarraySum(self, a, n):
		sum = 0
		m = 10 ** 9 + 7
		i = 0
		while i < n:
			sum = ((n - i) * (i + 1) * a[i] + sum) % m
			i += 1
		return int(sum % m)


class Solution:

	def subarraySum(self, a, n):
		k = 10 ** 9 + 7
		s = 0
		for i in range(n):
			s = s + a[i] * (i + 1) * (n - i)
		if s > k:
			return s % k
		else:
			return s


class Solution:

	def subarraySum(self, a, n):
		sum = 0
		k = 1
		p = n
		for i in range(0, n):
			sum += k * p * a[i]
			if n % 2 == 0:
				if i < n // 2 - 1:
					k += 1
					p -= 1
				elif i + 1 == n // 2:
					k = k
					p = p
				else:
					k -= 1
					p += 1
			elif i < (n + 1) // 2 - 1:
				k += 1
				p -= 1
			else:
				k -= 1
				p += 1
		return sum % 1000000007


class Solution:

	def subarraySum(self, a, n):
		mod = 1000000007
		sum = 0
		for i in range(n):
			ans = a[i] * (i + 1)
			ans = ans % mod * (n - i)
			ans = ans % mod
			sum += ans
			sum = sum % mod
		return sum


class Solution:

	def subarraySum(self, arr, n):
		addition = 0
		p = 1000000007
		for i in range(n):
			addition = (addition + arr[i] * (n - i) * (i + 1)) % p
		return addition % p


class Solution:

	def subarraySum(self, a, n):
		total = 0
		for i in range(n):
			row = i + 1
			col = n - i
			count_i = row * col
			total = total + a[i] * count_i
		return total % 1000000007


class Solution:

	def subarraySum(self, a, n):
		total = 0
		for i in range(len(a)):
			total += a[i] * ((i + 1) * (len(a) - i))
		return total % 1000000007


class Solution:

	def subarraySum(self, a, n):
		c = 0
		for j in range(n):
			q = n - j
			w = (n - j) * j
			s = q + w
			c += s * a[j]
		return c % 1000000007


class Solution:

	def subarraySum(self, a, n):
		mod = int(1000000000.0 + 7)
		presum = [0] * n
		ans = 0
		for (i, n) in enumerate(a):
			presum[i] = n if i == 0 else presum[i - 1] + n * (i + 1) % mod
			presum[i] %= mod
			ans += presum[i]
			ans %= mod
		return ans % mod