You are given an array A consisting of N positive integers.

Find \sum_{i=1}^{N} \sum_{j=i}^{N} F^{3}(i,j), where F(i,j)=\sum_{k=i}^{j} A_{k}.

Since the value might be quite large, print it modulo 998244353.

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

- The first line of input contains a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains an integer N — the length of the array A.
- The second line of each test case contains N space-separated integers A_{1},A_{2},\ldots,A_{N} representing the array A.

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

For each test case, output on a new line, the answer, modulo 998244353.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 5 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{6}$
- The sum of $N$ over all test cases won't exceed $5 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
2
1 1
3
1 2 1
5
8 5 6 2 3

----- Sample Output 1 ------ 
10
128
42621
----- explanation 1 ------ 
Test case $1$: $F(1, 1) = 1, F(1, 2) = 1+1=2, F(2, 2) = 1$. 

Thus, $\sum_{i=1}^{N} \sum_{j=i}^{N} F^{3}(i,j) = 1^{3} + 2^{3} + 1^{3} = 10$.

Test case $2$: $F(1, 1) = 1, F(1, 2) = 1+2=3, F(1, 3) = 1+2+1 =4, F(2, 2) = 2, F(2, 3) = 2+1=3, F(3, 3) = 1$. 

Thus, $\sum_{i=1}^{N} \sum_{j=i}^{N} F^{3}(i,j) = 1^{3} + 3^{3} + 4^{3}+2^{3}+3^{3}+1^{3} = 128$.

Difficulty: HARD
Tags: Mathematics

Range queries
Skill types: Range queries

Starter code:

Solutions:
MOD = 998244353
numTests = int(input(''))
for i in range(numTests):
	N = int(input(''))
	inp = input('').split()[:N]
	elems = [int(e) for e in inp]
	arr = elems
	sumStartingFrom = [0] * N
	sumSquaredStartingFrom = [0] * N
	sumStartingFrom[N - 1] = arr[N - 1] % MOD
	sumSquaredStartingFrom[N - 1] = arr[N - 1] * arr[N - 1] % MOD
	for i in range(2, N + 1):
		updateIndex = N - i
		sumStartingFrom[updateIndex] = sumStartingFrom[updateIndex + 1] + i * arr[updateIndex]
		sumStartingFrom[updateIndex] %= MOD
	for i in range(2, N + 1):
		updateIndex = N - i
		nextIndex = updateIndex + 1
		sumSquaredStartingFrom[updateIndex] = sumSquaredStartingFrom[nextIndex] + (i * arr[updateIndex] * arr[updateIndex] + 2 * arr[updateIndex] * sumStartingFrom[nextIndex])
		sumSquaredStartingFrom[updateIndex] %= MOD
	temp = arr[N - 1] ** 3 % MOD
	ans = temp
	for i in range(2, N + 1):
		updateIndex = N - i
		temp += i * arr[updateIndex] ** 3 % MOD
		temp += 3 * arr[updateIndex] ** 2 * sumStartingFrom[updateIndex + 1] % MOD
		temp += 3 * arr[updateIndex] * sumSquaredStartingFrom[updateIndex + 1] % MOD
		temp %= MOD
		ans += temp
		ans %= MOD
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list()
	v = 0
	for i in range(n):
		v += a[i]
		b.append(v)
	ans = 0
	st = n
	for i in range(n):
		ans = (ans + st * b[-1 - i] ** 3) % 998244353
		st -= 2
	v = 0
	w = 0
	b_sq = list()
	b_back = list()
	for i in range(n):
		v += b[i]
		b_sq.append(v)
		w += b[-1 - i]
		b_back.append(w)
	for i in range(n - 1):
		ans = (ans + 3 * (b_back[-i - 2] * b[i] * b[i] - b[i + 1] * b[i + 1] * b_sq[i])) % 998244353
	print(ans)


mod = 998244353
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	res = pref = 0
	sm1 = sm2 = sm3 = 0
	for i in range(n):
		pref += l[i]
		res += (i + 1) * pref ** 3
		res -= sm3
		res -= 3 * pref ** 2 * sm1
		res += 3 * pref * sm2
		sm1 += pref
		sm2 += pref ** 2
		sm3 += pref ** 3
	print(res % mod)


mod = 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	res = pref = 0
	sm1 = sm2 = sm3 = 0
	for i in range(n):
		pref += ar[i]
		res += (i + 1) * pref ** 3
		res -= sm3
		res -= 3 * pref ** 2 * sm1
		res += 3 * pref * sm2
		sm1 += pref
		sm2 += pref ** 2
		sm3 += pref ** 3
	print(res % mod)


T = 998244353
n = int(input())
for j in range(n):
	N = int(input())
	A = list(map(int, input().split()))
	ans = pf = 0
	sm1 = sm2 = sm3 = 0
	for i in range(N):
		pf += A[i]
		ans += (i + 1) * pf ** 3
		ans -= sm3
		ans -= 3 * pf ** 2 * sm1
		ans += 3 * pf * sm2
		sm1 += pf
		sm2 += pf ** 2
		sm3 += pf ** 3
	print(ans % T)


T = 998244353
for j in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	ans = pref = 0
	sum1 = sum2 = sum3 = 0
	for i in range(N):
		pref += A[i]
		ans += (i + 1) * pref ** 3
		ans -= sum3
		ans -= 3 * pref ** 2 * sum1
		ans += 3 * pref * sum2
		sum1 += pref
		sum2 += pref ** 2
		sum3 += pref ** 3
	print(ans % T)


T = 998244353
for j in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	ans = pref = 0
	psum = psum2 = psum3 = 0
	for i in range(N):
		pref += A[i]
		ans += (i + 1) * pref ** 3
		ans -= psum3
		ans -= 3 * pref ** 2 * psum
		ans += 3 * pref * psum2
		psum += pref
		psum2 += pref ** 2
		psum3 += pref ** 3
	print(ans % T)


i = int(input())
t = 998244353
for _ in range(i):
	n = int(input())
	a = list(map(int, input().split()))
	ans = pref = 0
	sum1 = sum2 = sum3 = 0
	for j in range(n):
		pref += a[j]
		ans += (j + 1) * pref ** 3
		ans -= sum3
		ans -= 3 * pref ** 2 * sum1
		ans += 3 * pref * sum2
		sum1 += pref
		sum2 += pref ** 2
		sum3 += pref ** 3
	print(ans % t)


t = int(input())
while t > 0:
	n = int(input())
	vec = [int(i) for i in input().split(' ')]
	sum = []
	sum.append(0)
	for i in vec:
		sum.append(sum[-1] + i)
	sumofsum = []
	sumofsum.append(0)
	for j in range(1, n + 1):
		sumofsum.append(sumofsum[-1] + sum[j])
	out = 0
	for i in range(n + 1):
		temp = sum[i] * sum[i] * sum[i]
		sq = sum[i] * sum[i]
		a = 2 * i - n
		out += a * temp
		x = -sumofsum[n] + sumofsum[i]
		if i > 1:
			x += sumofsum[i - 1]
		sq = sq * x
		out = out - 3 * sq
	print(out % 998244353)
	t -= 1


T = int(input())
C = 998244353
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	SUM = 0
	P = [0] * (N + 1)
	P[0] = 0
	for j in range(1, N + 1):
		P[j] = P[j - 1] + A[j - 1]
	Q = [0] * (N + 1)
	Q[0] = 0
	R = [0] * (N + 1)
	R[N] = P[N]
	for j in range(1, N + 1):
		Q[j] = Q[j - 1] + P[j]
		R[N - j] = R[N - j + 1] + P[N - j]
	S1 = 0
	S2 = 0
	S3 = 0
	S4 = 0
	for j in range(1, N + 1):
		S1 = (S1 + j * P[j] * P[j] * P[j]) % C
		S2 = (S2 + 3 * P[j - 1] * P[j - 1] * R[j]) % C
		S3 = (S3 + (N - j + 1) * P[j - 1] * P[j - 1] * P[j - 1]) % C
		S4 = (S4 + 3 * P[j] * P[j] * Q[j - 1]) % C
	SUM = (S1 + S2 - S3 - S4) % C
	print(SUM)


mod = 998244353
for _ in range(int(input())):
	N = int(input())
	A = [int(c) for c in input().split()]
	ans = pref = 0
	sum1 = sum2 = sum3 = 0
	for i in range(N):
		pref += A[i]
		ans += (i + 1) * pref ** 3
		ans -= sum3
		ans -= 3 * pref ** 2 * sum1
		ans += 3 * pref * sum2
		sum1 += pref
		sum2 += pref ** 2
		sum3 += pref ** 3
	print(ans % mod)


mod = 998244353
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = pref = 0
	psum = psum2 = psum3 = 0
	for i in range(n):
		pref += a[i]
		ans += (i + 1) * pref ** 3
		ans -= psum3
		ans -= 3 * pref ** 2 * psum
		ans += 3 * pref * psum2
		psum += pref
		psum2 += pref ** 2
		psum3 += pref ** 3
	print(ans % mod)


mod = 998244353
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = p = pp = ps = pc = 0
	for i in range(n):
		p = (p + a[i]) % mod
		ans = (ans + (i + 1) * p % mod * p % mod * p % mod) % mod
		ans = (ans - pc) % mod
		ans = (ans - 3 * (p * p % mod * pp) % mod % mod) % mod
		ans = (ans + 3 * (p * ps) % mod) % mod
		pp = (pp + p) % mod
		ps = (ps + p * p % mod) % mod
		pc = (pc + p * p % mod * p % mod) % mod
	print(ans)


for _ in range(int(input())):
	a1 = int(input())
	b = list(map(int, input().split()))
	arr = []
	s = 0
	s_ = 0
	s__ = 0
	for i in b:
		s += i
		s_ = s * s
		s__ = s_ * s
		arr.append([s, s_, s__])
	s1 = 0
	s2 = 0
	s3 = 0
	p1 = []
	for i in range(a1):
		s1 += arr[i][0]
		s2 += arr[i][1]
		s3 += arr[i][2]
		p1.append([s1, s2, s3])
	ans = 0
	for j in range(a1):
		if j >= 1:
			ans += (j + 1) * arr[j][2] + 3 * p1[j - 1][1] * arr[j][0] - 3 * arr[j][1] * p1[j - 1][0] - p1[j - 1][2]
		else:
			ans += arr[0][2]
	print(ans % 998244353)


mod = 998244353

def bin_power(num, power):
	exp = power
	ans = 1
	while exp:
		if exp % 2:
			ans = ans * num
			exp = exp - 1
		else:
			num = num * num
			exp = exp // 2
	return ans
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(pre_sum, res, post_pre_sum) = (0, 0, [0 for i in range(4)])
	for i in range(n):
		pre_sum += a[i]
		res += (i + 1) * bin_power(pre_sum, 3)
		res += 3 * pre_sum * post_pre_sum[2]
		res -= 3 * bin_power(pre_sum, 2) * post_pre_sum[1]
		res -= post_pre_sum[3]
		post_pre_sum[1] += pre_sum
		post_pre_sum[2] += bin_power(pre_sum, 2)
		post_pre_sum[3] += bin_power(pre_sum, 3)
	print(res % mod)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	p = []
	sum = 0
	for i in range(n):
		sum += A[i]
		sum2 = sum * sum
		sum3 = sum2 * sum
		p.append((sum, sum2, sum3))
	pre = []
	s1 = 0
	s2 = 0
	s3 = 0
	for i in range(n):
		s1 += p[i][0]
		s2 += p[i][1]
		s3 += p[i][2]
		pre.append((s1, s2, s3))
	ans = 0
	for j in range(n):
		if j >= 1:
			ans += (j + 1) * p[j][2] + 3 * pre[j - 1][1] * p[j][0] - 3 * p[j][1] * pre[j - 1][0] - pre[j - 1][2]
		else:
			ans += p[0][2]
	print(ans % 998244353)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	psum = 0
	mod = 998244353
	pre = []
	for i in range(4):
		pre.append(0)
	for i in range(n):
		psum += a[i]
		psum %= mod
		ans += (i + 1) * psum ** 3
		ans -= 3 * pre[1] * (psum * psum)
		ans += 3 * pre[2] * psum
		ans -= pre[3]
		ans %= mod
		ans = (ans + mod) % mod
		pre[1] += psum
		pre[2] += psum * psum
		pre[3] += psum ** 3
		pre[1] %= mod
		pre[2] %= mod
		pre[3] %= mod
	print(ans)


Num = 998244353
for _ in range(int(input())):
	num1 = int(input())
	li = list(map(int, input().split()))
	pre = [0] * 3
	answer = 0
	bala = 0
	for i in range(num1):
		bala += li[i]
		answer += (i + 1) * pow(bala, 3)
		answer -= 3 * pre[0] * pow(bala, 2)
		answer += 3 * pre[1] * bala
		answer -= pre[2]
		pre[0] += bala
		pre[1] += pow(bala, 2)
		pre[2] += pow(bala, 3)
	print(answer % Num)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	prefix = [0]
	s = 0
	for i in l:
		s += i
		prefix.append(s)
	c = 0
	x = 0
	r = sum(prefix)
	for i in range(len(prefix)):
		r -= prefix[i]
		c += prefix[i] ** 2 * (x - r)
		x += prefix[i]
	cal = 0
	for i in range(len(prefix)):
		cal += prefix[i] ** 3 * (i - (len(prefix) - (1 + i)))
	print((cal - 3 * c) % 998244353)


N = 998244353
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	pre = [0] * 3
	ans = 0
	psum = 0
	for i in range(n):
		psum += l[i]
		ans += (i + 1) * pow(psum, 3)
		ans -= 3 * pre[0] * pow(psum, 2)
		ans += 3 * pre[1] * psum
		ans -= pre[2]
		pre[0] += psum
		pre[1] += pow(psum, 2)
		pre[2] += pow(psum, 3)
	print(ans % N)


from functools import reduce
t = int(input())
while t > 0:
	n = int(input())
	l1 = input('')
	l2 = l1.split(' ')
	l = list(map(int, l2))
	s2 = []
	a1 = 0
	for i in range(n):
		s2.append(a1)
		a1 = a1 + l[i]
	s2.append(a1)
	s1 = list(map(int, s2))
	ans1 = 0
	for i in range(0, n + 1):
		ans1 = ans1 + s1[i] * s1[i] * s1[i] * (i - (n - i))
	temp1 = 0
	temp2 = reduce(lambda x, y: x + y, s1)
	ans2 = 0
	for i in range(n + 1):
		temp2 = temp2 - s1[i]
		ans2 = ans2 + (temp1 - temp2) * (s1[i] * s1[i])
		temp1 = temp1 + s1[i]
	ans = (ans1 - 3 * ans2) % 998244353
	print(ans)
	t -= 1


for x in range(int(input())):
	abc = int(input())
	bcd = list(map(int, input().split()))
	cde = []
	temp = 0
	for i in bcd:
		cde.append(temp)
		temp += i
	cde.append(temp)
	bcd = cde[:]
	abc = len(bcd)
	temp1 = 0
	for i in range(abc):
		temp1 += bcd[i] ** 3 * (i - (abc - (1 + i)))
	temp2 = 0
	left = 0
	right = sum(bcd)
	for i in range(abc):
		right -= bcd[i]
		temp2 += bcd[i] ** 2 * (left - right)
		left += bcd[i]
	print((temp1 - 3 * temp2) % 998244353)


mod = 998244353
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	pre = [0] * 3
	ans = 0
	psum = 0
	for i in range(n):
		psum += arr[i]
		ans += (i + 1) * pow(psum, 3)
		ans -= 3 * pre[0] * pow(psum, 2)
		ans += 3 * pre[1] * psum
		ans -= pre[2]
		pre[0] += psum
		pre[1] += pow(psum, 2)
		pre[2] += pow(psum, 3)
	print(ans % mod)


for x in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	m = 998244353
	tp = 0
	c = []
	for i in b:
		c.append(tp)
		tp = tp + i
	c.append(tp)
	b = c[:]
	tp1 = 0
	a = len(b)
	for i in range(a):
		k = (i - (a - (i + 1))) * (b[i] * b[i] * b[i])
		tp1 = tp1 + k
	r = sum(b)
	l = 0
	tp2 = 0
	for i in range(a):
		r = r - b[i]
		tp2 = tp2 + (l - r) * (b[i] * b[i])
		l = l + b[i]
	ans = tp1 - 3 * tp2
	ans %= m
	print(ans)


mod = 998244353
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	summ = 0
	p = 0
	ps = 0
	pc = 0
	ans = 0
	for i in range(n):
		summ += l[i]
		ans += (i + 1) * summ ** 3
		ans -= pc
		ans -= 3 * summ ** 2 * p
		ans += 3 * summ * ps
		ans %= mod
		p += summ
		ps += summ ** 2
		pc += summ ** 3
	print(ans)


for _ in range(int(input())):
	ant = int(input())
	bat = list(map(int, input().split()))
	cat = []
	nick = 0
	for i in bat:
		cat.append(nick)
		nick += i
	cat.append(nick)
	bat = cat[:]
	at = len(bat)
	nick1 = 0
	for i in range(at):
		nick1 += bat[i] ** 3 * (i - (at - (1 + i)))
	nick2 = 0
	left_side = 0
	right_side = sum(bat)
	for i in range(at):
		right_side -= bat[i]
		nick2 += bat[i] ** 2 * (left_side - right_side)
		left_side += bat[i]
	print((nick1 - 3 * nick2) % 998244353)


for x in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	c = []
	temp = 0
	for i in b:
		c.append(temp)
		temp += i
	c.append(temp)
	b = c[:]
	a = len(b)
	temp1 = 0
	for i in range(a):
		temp1 += b[i] ** 3 * (i - (a - (1 + i)))
	temp2 = 0
	left = 0
	right = sum(b)
	for i in range(a):
		right -= b[i]
		temp2 += b[i] ** 2 * (left - right)
		left += b[i]
	print((temp1 - 3 * temp2) % 998244353)


def mult(a, b, c, d):
	temp = 0
	temp = a * b * c * d
	return temp

def fill(l1, n, l2):
	l2.append(l1[0])
	for i in range(1, n):
		l2.append(l2[i - 1] + l1[i])
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	first1 = []
	first2 = []
	fill(l, n, first1)
	fill(first1, n, first2)
	result = 0
	for i in range(n):
		result += mult(i + 1, first1[i], first1[i], first1[i])
		if i != 0:
			result -= mult(3, first1[i], first1[i], first2[i - 1])
		result -= mult(n - 1 - i, first1[i], first1[i], first1[i])
		result += mult(3, first2[n - 1] - first2[i], first1[i], first1[i])
	print(result % 998244353)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	L = []
	tem = 0
	for i in A:
		L.append(tem)
		tem += i
	L.append(tem)
	A = L[:]
	N = len(A)
	tem = 0
	for i in range(N):
		tem += A[i] ** 3 * (i - (N - (1 + i)))
	tem2 = 0
	l = 0
	r = sum(A)
	for i in range(N):
		r -= A[i]
		tem2 += A[i] ** 2 * (l - r)
		l += A[i]
	print((tem - 3 * tem2) % 998244353)


def solve():
	n = int(input())
	nums = list(map(int, input().split()))
	prefixes = [0] * (n + 1)
	for i in range(1, n + 1):
		prefixes[i] = prefixes[i - 1] + nums[i - 1]
	ans = 0
	tmp1 = 0
	for i in range(n + 1):
		tmp1 += prefixes[i] ** 3 * (2 * i - n)
	tmp2 = 0
	l = 0
	r = sum(prefixes)
	for i in range(n + 1):
		r -= prefixes[i]
		tmp2 += prefixes[i] ** 2 * (l - r)
		l += prefixes[i]
	print((tmp1 - 3 * tmp2) % 998244353)

def main():
	T = int(input())
	while T:
		solve()
		T -= 1
main()


t = int(input())
for x in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	c = []
	res = 0
	for i in arr:
		c.append(res)
		res += i
	c.append(res)
	arr = c[:]
	n = len(arr)
	temp = 0
	for i in range(n):
		temp += arr[i] ** 3 * (i - (n - (1 + i)))
	temp1 = 0
	temp2 = 0
	temp3 = sum(arr)
	for i in range(n):
		temp3 -= arr[i]
		temp1 += arr[i] ** 2 * (temp2 - temp3)
		temp2 += arr[i]
	print((temp - 3 * temp1) % 998244353)


for x in range(int(input())):
	var1 = int(input())
	var2 = list(map(int, input().split()))
	var3 = []
	t = 0
	for i in var2:
		var3.append(t)
		t += i
	var3.append(t)
	var2 = var3[:]
	var1 = len(var2)
	temp1 = 0
	for i in range(var1):
		temp1 += var2[i] ** 3 * (i - (var1 - (1 + i)))
	temp2 = 0
	left = 0
	right = sum(var2)
	for i in range(var1):
		right -= var2[i]
		temp2 += var2[i] ** 2 * (left - right)
		left += var2[i]
	print((temp1 - 3 * temp2) % 998244353)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	b = [0] * n
	c = [0] * n
	d = [0] * n
	e = [0] * n
	a = 0
	m = 0
	p = 0
	q = 0
	for i in range(n):
		a = a + l[i]
		q = q + a
		m = m + a * a
		p = p + a * a * a
		e[i] = a
		b[i] = q
		c[i] = m
		d[i] = p
	s = d[n - 1]
	for i in range(1, n):
		x = (n - i) * e[i - 1] ** 3
		y = 3 * e[i - 1] * (c[n - 1] - c[i - 1])
		z = 3 * e[i - 1] ** 2 * (b[n - 1] - b[i - 1])
		w = d[n - 1] - d[i - 1]
		s = s + w - x + z - y
	print(s % 998244353)


mod = 998244353
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = [0] * n
	s1 = 0
	s2 = 0
	s3 = 0
	r1 = a[n - 1] % mod
	r2 = r1 * r1 % mod
	r3 = r2 * r1 % mod
	s1 = r1
	s2 = r2
	s3 = r3
	ans = s3 % mod
	c = 2
	for i in range(n - 2, -1, -1):
		r1 = a[i] % mod
		r2 = r1 * r1 % mod
		r3 = r2 * r1 % mod
		s3 = (s3 + 3 * r2 * s1 + 3 * r1 * s2 + c * r3) % mod
		s2 = (s2 + 2 * s1 * r1 + c * r2) % mod
		s1 = (s1 + c * r1) % mod
		c += 1
		ans = (ans + s3) % mod
	print(ans)


import heapq
import operator
import itertools
import sys
import functools
import bisect
import math
import random
import statistics
from collections import Counter
RTM1 = 1000000000.0 + 7
RTM2 = 998244353

def fact(n):
	if n == 1 or n == 0:
		return 1
	return n * fact(n - 1)

def prod(a, b):
	if a == 0 or b == 0:
		return 0
	return a + prod(a, b - 1)
for _ in range(int(input())):
	ravi = int(input())
	teja = [int(x) for x in input().split()]
	tr1 = teja[-1] % RTM2
	tr2 = tr1 * tr1 % RTM2
	tr3 = tr2 * tr1 % RTM2
	rt1 = tr1
	rt2 = tr2
	rt3 = tr3
	rtc = 2
	kamsu = rt3 % RTM2
	for i in range(ravi - 2, -1, -1):
		tr1 = teja[i] % RTM2
		tr2 = tr1 * tr1 % RTM2
		tr3 = tr2 * tr1 % RTM2
		rt3 = (rt3 + 3 * tr2 * rt1 + 3 * tr1 * rt2 + rtc * tr3) % RTM2
		rt2 = (rt2 + 2 * tr1 * rt1 + rtc * tr2) % RTM2
		rt1 = (rt1 + rtc * tr1) % RTM2
		rtc += 1
		kamsu = (kamsu + rt3) % RTM2
	print(kamsu)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = []
	t = 0
	for j in l:
		s.append(t)
		t += j
	s.append(t)
	l = s[:]
	n = len(l)
	t1 = 0
	for j in range(n):
		t1 += l[j] ** 3 * (j - (n - (1 + j)))
	t2 = 0
	lft = 0
	rht = sum(l)
	for j in range(n):
		rht -= l[j]
		t2 += l[j] ** 2 * (lft - rht)
		lft += l[j]
	print((t1 - 3 * t2) % 998244353)


t = int(input())
for i in range(t):
	n = int(input())
	l1 = []
	l = list(map(int, input().split()))
	tem = tem1 = tem2 = counterl = counterr = 0
	for i in range(n):
		l1.append(tem)
		tem += l[i]
	l1.append(tem)
	for i in range(n + 1):
		tem1 = tem1 + l1[i] ** 3 * (i - (n + 1 - (i + 1)))
	for i in l1:
		counterr += i
	for i in range(n + 1):
		counterr = counterr - l1[i]
		tem2 += l1[i] ** 2 * (counterl - counterr)
		counterl = counterl + l1[i]
	print((tem1 - 3 * tem2) % 998244353)


N = 998244353
for j in range(int(input())):
	c = [0]
	d = [0]
	d2 = [0]
	d3 = [0]
	n = int(input())
	a = [int(x) for x in input().split()]
	for i in range(n):
		c.append(c[i] + a[i])
		d.append(d[i] + c[i + 1])
		d2.append(d2[i] + c[i + 1] * c[i + 1])
		d3.append(d3[i] + c[i + 1] * c[i + 1] * c[i + 1])
	s = 0
	for i in range(1, n + 1):
		s = s + i * c[i] * c[i] * c[i] - 3 * c[i] * c[i] * d[i - 1] + 3 * c[i] * d2[i - 1] - d3[i - 1]
	s = s % N
	print(s)


modulo = 998244353
for _ in range(int(input())):
	n = int(input())
	hello = list(map(int, input().split()))
	array = []
	mcbc = 0
	array.append(mcbc)
	for i in hello:
		mcbc += i
		array.append(mcbc)
	n += 1
	mcbc = 0
	for i in range(n):
		mcbc += array[i] ** 3 * (i - (n - (i + 1)))
	tatti = 0
	l = 0
	ravikant = sum(array)
	for i in array:
		ravikant -= i
		tatti += i ** 2 * (l - ravikant)
		l += i
	print((mcbc - 3 * tatti) % modulo)


mod = 998244353
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = [0] * n
	s1 = 0
	s2 = 0
	s3 = 0
	rem1 = a[n - 1] % mod
	rem2 = rem1 * rem1 % mod
	rem3 = rem2 * rem1 % mod
	s1 = rem1
	s2 = rem2
	s3 = rem3
	ans = s3 % mod
	c = 2
	for i in range(n - 2, -1, -1):
		rem1 = a[i] % mod
		rem2 = rem1 * rem1 % mod
		rem3 = rem2 * rem1 % mod
		s3 = (s3 + 3 * rem2 * s1 + 3 * rem1 * s2 + c * rem3) % mod
		s2 = (s2 + 2 * s1 * rem1 + c * rem2) % mod
		s1 = (s1 + c * rem1) % mod
		c += 1
		ans = (ans + s3) % mod
	print(ans)


for flag in range(int(input())):
	first1 = int(input())
	second2 = list(map(int, input().split()))
	third3 = []
	temporary = 0
	for a in second2:
		third3.append(temporary)
		temporary += a
	third3.append(temporary)
	second2 = third3[:]
	first1 = len(second2)
	temp1 = 0
	for a in range(first1):
		temp1 += second2[a] ** 3 * (a - (first1 - (1 + a)))
	temp2 = 0
	leftHand = 0
	rightHand = sum(second2)
	for a in range(first1):
		rightHand -= second2[a]
		temp2 += second2[a] ** 2 * (leftHand - rightHand)
		leftHand += second2[a]
	print((temp1 - 3 * temp2) % 998244353)


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	c = []
	temp = 0
	for i in arr:
		c.append(temp)
		temp += i
	c.append(temp)
	arr = c[:]
	n = len(arr)
	x = 0
	for i in range(n):
		x += arr[i] ** 3 * (i - (n - (1 + i)))
	y = 0
	left = 0
	right = sum(arr)
	for i in range(n):
		right -= arr[i]
		y += arr[i] ** 2 * (left - right)
		left += arr[i]
	print((x - 3 * y) % 998244353)


for t in range(int(input())):
	n = int(input())
	N = list(map(int, input().split()))
	m = []
	t = 0
	for i in N:
		m.append(t)
		t += i
	m.append(t)
	N = m[:]
	a = len(N)
	t1 = 0
	for i in range(a):
		t1 += N[i] ** 3 * (i - (a - (1 + i)))
	t2 = 0
	l = 0
	r = sum(N)
	for i in range(a):
		r -= N[i]
		t2 += N[i] ** 2 * (l - r)
		l += N[i]
	print((t1 - 3 * t2) % 998244353)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	pre = []
	s = 0
	for x in a:
		pre.append(s)
		s += x
	pre.append(s)
	a = pre[:]
	n = len(a)
	s1 = 0
	for i in range(n):
		s1 += a[i] ** 3 * (i - (n - (i + 1)))
	s2 = 0
	l = 0
	r = sum(a)
	for i in range(n):
		r -= a[i]
		s2 += a[i] ** 2 * (l - r)
		l += a[i]
	print((s1 - s2 * 3) % 998244353)