Chef has an array A consisting of N integers (1-based indexing). He asks you to perform the following operation M times:

	for i = 2 to N:
		Ai = Ai + Ai-1

Your task is to find the xth element of the array (i.e., Ax) after performing the above operation M times. As the answer could be large, please output it modulo 109 + 7.

-----Input-----
- The first line of input contains an integer T denoting the number of test cases.
- The first line of each test case contains three space-separated integers — N, x, and M — denoting the size of the array, index of the element you need to find, and the amount of times you need to repeat operation before finding the element, respectively. The second line contains N space-separated integers A1, A2, …, AN.

-----Output-----
For each test case, output a single line containing one integer: Ax modulo 109 + 7. 

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ x ≤ N ≤ 105
- 1 ≤ M ≤ 1018 
- 1 ≤ Ai  ≤ 1018

-----Subtasks-----Subtask 1 (8 points):
- 1 ≤ x ≤ min{2, N}Subtask 2 (24 points):
- 1 ≤ N * M ≤ 106Subtask 3 (68 points):  No additional constraints

-----Example-----
Input:
2
3 2 3
1 2 3
3 3 3 
1 2 3

Output:
5
15

-----Explanation-----
Values in the array A:
- Before the operations: [1, 2, 3]
- After the first operation: [1, 3, 6]
- After the second operation: [1, 4, 10]
- After the third operation: [1, 5, 15]

Since input file can be fairly large (about 8 MB), it's recommended to use fast I/O (for example, in C++, use scanf/printf instead of cin/cout).

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
import math
T = int(input())
for i in range(T):
	(n, x, m) = map(int, input().split())
	l1 = [int(i) for i in input().split()]
	if x == 1:
		l1[0] = l1[0] % 1000000007
		print(l1[0])
	elif x == 2:
		m = m % 1000000007
		l1[0] = l1[0] % 1000000007
		l1[1] = (l1[1] % 1000000007 + l1[0] * m % 1000000007) % 1000000007
		print(l1[1])
	else:
		m = m % 1000000007
		c = -1
		y = 0
		q = 1
		f = 1
		y = l1[x - 1] % 1000000007
		for j in range(x - 2, -1, -1):
			c = c + 1
			q = q * ((m + c) % 1000000007) % 1000000007
			q = q * pow(c + 1, 1000000005, 1000000007) % 1000000007
			y = (y + q * (l1[j] % 1000000007) % 1000000007) % 1000000007
		print(y % 1000000007)


emod = 1000000007
save_list = []
inverse = [1337]

def modpow(n, k):
	if k == 0:
		return 1
	if k % 2 == 0:
		return modpow(n * n % emod, k // 2)
	else:
		return modpow(n * n % emod, k // 2) * n % emod

def GenInvers():
	i = 1
	while i <= 100005:
		inverse.append(modpow(i, emod - 2))
		i += 1

def choose(n, k):
	k = n - k
	res = 1
	i = 1
	while i <= k:
		res = res * (n - k + i) * inverse[i] % emod
		save_list.append(res)
		i += 1
t = int(input())
GenInvers()
for curent_test in range(t):
	nxm = input().split()
	n = int(nxm[0])
	x = int(nxm[1])
	m = int(nxm[2]) - 1
	sum = 0
	inp = input().split()
	save_list = [1]
	choose(m + (x - 1), m)
	i = x - 1
	j = 0
	while i >= 0:
		Ai = int(inp[i]) % emod
		temp = Ai * save_list[j]
		if temp >= emod:
			temp %= emod
		sum += temp
		if sum >= emod:
			sum %= emod
		i -= 1
		j += 1
	print(sum)


for _ in range(int(input())):
	(n, x, m) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	q = []
	for j in range(m):
		for i in range(1, len(l)):
			l[i] = l[i] + l[i - 1]
	print(l[x - 1] % (10 ** 9 + 7))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
t = int(input())
for _ in range(t):
	(n, select, m) = map(int, input().split())
	m = m % 1000000007
	arr = list(map(int, input().split()))
	for i in range(select):
		arr[i] = arr[i] % 1000000007
	ans = arr[select - 1]
	temp = 1
	tp = 0
	for i in range(select - 2, -1, -1):
		temp = temp * (m + tp) % 1000000007
		q = modinv(tp + 1, 1000000007)
		temp = temp * q % 1000000007
		ans += arr[i] * temp
		ans = ans % 1000000007
		tp += 1
	print(ans % 1000000007)


T = int(input())
for i in range(T):
	(n, x, m) = list(map(int, input().split()))
	l1 = [int(i) for i in input().split()]
	if x == 1:
		l1[0] = l1[0] % 1000000007
		print(l1[0])
	elif x == 2:
		m = m % 1000000007
		l1[0] = l1[0] % 1000000007
		l1[1] = (l1[1] % 1000000007 + l1[0] * m % 1000000007) % 1000000007
		print(l1[1])


p = 10 ** 9 + 7
f = [1] * (100000 + 1)
for i in range(1, 100000 + 1):
	f[i] = i * f[i - 1]
	if f[i] > p:
		f[i] = f[i] % p
for _ in range(int(input())):
	(n, x, m) = map(int, input().split())
	m = m % p
	a = list(map(int, input().split()))
	pre = [1] * x
	for i in range(1, x):
		pre[i] = pre[i - 1] % p * ((m + (i - 1)) % p) % p % p * (f[i - 1] % p) % p
		pre[i] = pre[i] // f[i]
	ans = 0
	j = 0
	for i in range(x - 1, -1, -1):
		ans += a[j] * pre[i]
		if ans > p:
			ans = ans % p
		j += 1
	print(ans % p)


t = int(input())
s = ''

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
for i in range(t):
	(n, x, m) = map(int, input().split())
	m %= 1000000007
	A = list(map(int, input().split()))
	ans = A[x - 1]
	temp = 1
	val = 0
	for i in range(x - 2, -1, -1):
		x = modinv(val + 1, 1000000007)
		temp = temp * (m + val) * x % 1000000007
		A[i] %= 1000000007
		ans += A[i] * temp
		ans %= 1000000007
		val += 1
	s += str(ans % 1000000007) + '\n'
print(s, end='')


MOD = 1000000007
arr = []

def calc(m, x):
	num = (m - 1) % MOD
	den = 0
	i = 0
	curEle = 1
	ans = 0
	ans += arr[x - i] * curEle
	ans = ans % MOD
	num += 1
	den += 1
	i += 1
	while i < x:
		curEle = curEle % MOD * (num % MOD) % MOD * pow(den, MOD - 2, MOD) % MOD
		ans += arr[x - i] * curEle
		ans = ans % MOD
		num += 1
		den += 1
		i += 1
	return ans
t = int(input())
for i in range(t):
	line = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.insert(0, 0)
	n = line[0]
	x = line[1]
	m = line[2]
	ans = calc(m, x)
	print(ans)


def mult(r, v):
	w = r
	for k in range(1, v):
		w = w * ((k + r) % 1000000007) % 1000000007
	return w
T = int(input())
for i in range(T):
	(n, x, m) = list(map(int, input().split()))
	l1 = [int(i) for i in input().split()]
	if x == 1:
		l1[0] = l1[0] % 1000000007
		print(l1[0])
	elif x == 2:
		m = m % 1000000007
		l1[0] = l1[0] % 1000000007
		l1[1] = (l1[1] % 1000000007 + l1[0] * m % 1000000007) % 1000000007
		print(l1[1])
	else:
		m = m % 1000000007
		c = 0
		y = 0
		y = l1[x - 1] % 1000000007
		for j in range(x - 2, -1, -1):
			c = c + 1
			s = mult(m, c) * pow(c, 1000000005, 1000000007) % 1000000007
			y = (y + s * (l1[j] % 1000000007) % 1000000007) % 1000000007
		print(y)


def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
p = 10 ** 9 + 7
f = [1] * (100000 + 1)
for i in range(1, 100000 + 1):
	f[i] = i * f[i - 1]
	if f[i] > p:
		f[i] = f[i] % p
for _ in range(int(input())):
	(n, x, m) = map(int, input().split())
	m = m % p
	a = list(map(int, input().split()))
	pre = [1] * x
	for i in range(1, x):
		pre[i] = pre[i - 1] * (m + (i - 1)) * f[i - 1]
		inv = modInverse(f[i], p)
		pre[i] = pre[i] * inv % p
	ans = 0
	j = 0
	for i in range(x - 1, -1, -1):
		ans += a[j] * pre[i]
		if ans > p:
			ans = ans % p
		j += 1
	print(ans % p)


MOD = 10 ** 9 + 7
for t in range(int(input())):
	(n, x, m) = map(int, input().split())
	a = list(map(int, input().split()))
	(v, c) = (a[x - 1] % MOD, 1)
	for i in range(1, x):
		c = c * (m + i - 1) * pow(i, MOD - 2, MOD) % MOD
		v = (v + c * a[x - 1 - i]) % MOD
	print(v)


p = 10 ** 9 + 7
N = [1, 1]
for i in range(2, 10 ** 5 + 1):
	N.append(pow(i, p - 2, p) * N[-1] % p)
for _ in range(int(input())):
	(n, x, m) = map(int, input().split())
	a = [0] + list(map(int, input().split()))
	(val, total) = (m % p, a[x] % p)
	for i in range(x - 1, 0, -1):
		total = (a[i] * val * N[x - i] + total) % p
		val = val * ((m + x - i) % p) % p
	print(total)


for _ in range(int(input())):
	(n, x, m) = map(int, input().split())
	a = [int(i) for i in input().split()]
	ans = a[x - 1]
	f = 1
	for i in range(1, x):
		f = f * (m - 1 + i)
		f = f // i
		ans += a[x - 1 - i] * f
	print(ans % (10 ** 9 + 7))


MOD = 1000000007
MMI = lambda A, n, s=1, t=0, N=0: (n < 2 and t % N or MMI(n, A % n, t, s - A // n * t, N or n), -1)[n < 1]
t = int(input())
for test in range(t):
	(n, x, m) = map(int, input().split())
	ls = list(map(int, input().split()))
	for i in range(n):
		ls[i] = ls[i] % MOD
	(su, y, m) = (0, m, m - 1)
	ml = [0 for i in range(x)]
	(n, d, ml[0]) = (m % MOD, m % MOD, 1)
	for i in range(1, x):
		ml[i] = ml[i - 1] * (n + 1) % MOD
		d = MMI(n + 1 - m, MOD)
		ml[i] = ml[i] * d % MOD
		n += 1
	ml = ml[::-1]
	for i in range(x):
		su = (su + ml[i] * ls[i] % MOD) % MOD
	print(su)


p = 10 ** 9 + 7
f = [0] * (10 ** 5 + 1)
f[0] = f[1] = 1
for z in range(2, 10 ** 5 + 1):
	f[z] = z * f[z - 1] % p
t = int(input())
for i in range(t):
	(n, x, m) = map(int, input().split())
	a = list(map(int, input().split()))
	c = [1] * x
	ans = 0
	j = 0
	m %= p
	for y in range(1, x):
		c[y] = c[y - 1] * (m + (y - 1)) * f[y - 1] * pow(f[y], p - 2, p) % p
	for u in range(x - 1, -1, -1):
		ans = (ans + c[u] * a[j]) % p
		j += 1
	print(ans % p)


modulo = 1000000007
food = []
t = int(input())
for x in range(1, 100001):
	food.append(pow(x, modulo - 2, modulo))
for i in range(t):
	s = input()
	s = s.split(' ')
	n = int(s[0])
	x = int(s[1])
	m = int(s[2])
	l = input().split(' ')
	q = int(l[x - 1]) % modulo
	multi = 1
	for j in range(x - 1):
		multi = multi * m * food[j] % modulo
		m += 1
		q = q + multi * int(l[x - 2 - j]) % modulo
	print(q % modulo)


MOD = 1000000007
MAXN = 100005
INV_MOD = [0] * MAXN

def MOD_POW(a, b):
	ret = int(1)
	while b > 0:
		if b & 1:
			ret = ret * a
			ret %= MOD
		a = a * a
		a %= MOD
		b //= 2
	return ret

def PREPROCESS():
	for i in range(1, MAXN):
		INV_MOD[i] = MOD_POW(int(i), MOD - 2)

def solve():
	s = input()
	(N, X, M) = s.strip().split(' ')
	N = int(N)
	X = int(X)
	M = int(M)
	s = input()
	A = [int(x) for x in s.strip().split(' ')]
	ans = int(0)
	coeff = int(1)
	j = int(1)
	for i in range(X - 1, -1, -1):
		ans = ans + A[i] * coeff
		coeff = coeff * (M + j - 1)
		coeff = coeff * INV_MOD[j]
		ans %= MOD
		coeff %= MOD
		j += 1
	print(ans)

def main():
	PREPROCESS()
	t = int(input())
	while t > 0:
		solve()
		t -= 1
main()


for _ in range(int(input())):
	(n, x, m) = list(map(int, input().split()))
	l = [int(i) for i in input().split()]
	MOD = 10 ** 9 + 7
	temp = l[:]
	while m:
		for i in range(1, n):
			l[i] = l[i] + l[i - 1]
		m -= 1
	print(l[x - 1] % MOD)


MOD = 10 ** 9 + 7
d = dict()

def power(x, y):
	if not y:
		return 1
	p = power(x, y // 2) % MOD
	p = p * p % MOD
	if y & 1:
		return x * p % MOD
	return p % MOD

def mod_inverse(x):
	if x in d:
		return d[x]
	d[x] = power(x, MOD - 2)
	return d[x]
t = int(input())
for _ in range(t):
	(n, x, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = arr[x - 1] % MOD
	p = 1
	for i in range(x - 2, -1, -1):
		p = p * (m + x - i - 2) * mod_inverse(x - i - 1) % MOD
		ans = (ans + p * arr[i]) % MOD
	print(ans)


for _ in range(int(input())):
	(n, x, m) = list(map(int, input().split()))
	l = [int(i) for i in input().split()]
	MOD = 10 ** 9 + 7
	if x <= 2:
		if x == 1:
			print(l[0] % MOD)
		else:
			print((l[0] * m + l[1]) % MOD)
		continue
	temp = l[:]
	while m:
		for i in range(1, n):
			l[i] = l[i] + l[i - 1]
		m -= 1
	print(l[x - 1] % MOD)


T = int(input())
for k in range(T):
	(n, x, m) = list(map(int, input().split()))
	l1 = [int(i) for i in input().split()]
	(l2, l3) = ([], [])
	for i in range(len(l1)):
		l2.append(0)
		l3.append(0)
	l2[0] = l1[0] % 1000000007
	for i in range(1, len(l1)):
		l2[i] = (l1[i] % 1000000007 + l2[i - 1] % 1000000007) % 1000000007
	if m == 1:
		print(l1[x - 1] % 1000000007)
	elif m == 2:
		print(l2[x - 1])
	else:
		l3[0] = l2[0]
		l3[1] = (l1[1] + m * l1[0] % 1000000007) % 1000000007
		s = 0
		v = 0
		for i in range(2, x):
			s = l2[i - 1] * (l2[i - 1] - 1) // 2
			v = l3[i - 1] * (l3[i - 1] + 1) // 2
			l3[i] = ((v - s) % 1000000007 + l1[i]) % 1000000007
	print(l3[x - 1])


import sys
MOD = 10 ** 9 + 7
f = sys.stdin
T = int(f.readlines(1)[0])
for t in range(T):
	(N, X, M) = map(int, f.readlines(1)[0].split())
	A = list(map(int, f.readlines(1)[0].split()))
	X -= 1
	sol = A[X] % MOD
	i = X - 1
	cnt = 0
	nCr = 1
	while i >= 0:
		cnt += 1
		nCr = nCr * (M + cnt - 1) % MOD
		nCr = nCr * pow(cnt, MOD - 2, MOD) % MOD
		sol = (sol + A[i] * nCr) % MOD
		i -= 1
	print(sol)


T = int(input())
for i in range(T):
	(n, x, m) = list(map(int, input().split()))
	l1 = [int(i) for i in input().split()]
	if x == 1:
		l1[0] = l1[0] % 1000000007
		print(l1[0])
	elif x == 2:
		m = m % 1000000007
		l1[0] = l1[0] % 1000000007
		l1[1] = (l1[1] % 1000000007 + l1[0] * m % 1000000007) % 1000000007
		print(l1[1])
	else:
		m = m % 1000000007
		c = -1
		y = 0
		q = 1
		y = l1[x - 1] % 1000000007
		for j in range(x - 2, -1, -1):
			c = c + 1
			q = q * ((m + c) % 1000000007) % 1000000007
			print(q)
			s = q * pow(c, 1000000005, 1000000007) % 1000000007
			y = (y + s * (l1[j] % 1000000007) % 1000000007) % 1000000007
		print(y)


f = []
t = int(input())
mod = 1000000007
for i in range(1, 100001):
	f.append(pow(i, mod - 2, mod))
for i in range(t):
	mul = 1
	s = input().split(' ')
	l = input().split(' ')
	x = int(s[1])
	mp = int(s[2])
	q = int(l[x - 1]) % mod
	for j in range(x - 1):
		mul = mul * mp * f[j] % mod
		mp += 1
		q = q + mul * int(l[x - 2 - j]) % mod
	print(q % mod)


p = 10 ** 9 + 7
f = [0] * (10 ** 5 + 1)
f[0] = f[1] = 1
for i in range(2, 10 ** 5 + 1):
	f[i] = i * f[i - 1] % p
for _ in range(int(input())):
	(n, x, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	pre = [1] * x
	ans = 0
	j = 0
	m = m % p
	for i in range(1, x):
		pre[i] = pre[i - 1] * (m + (i - 1)) * f[i - 1] * pow(f[i], p - 2, p) % p
	for i in range(x - 1, -1, -1):
		ans = (ans + pre[i] * a[j]) % p
		j += 1
	print(ans % p)


MOD = 1000000007
MMI = lambda A, n, s=1, t=0, N=0: (n < 2 and t % N or MMI(n, A % n, t, s - A // n * t, N or n), -1)[n < 1]

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a):
	(g, x, y) = egcd(a, MOD)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % MOD
t = int(input())
for test in range(t):
	(n, x, m) = map(int, input().split())
	ls = list(map(int, input().split()))
	for i in range(n):
		ls[i] = ls[i] % MOD
	su = 0
	y = m
	m = m - 1
	su = 0
	ml = [0 for i in range(x)]
	ml[0] = 1
	(n, d) = (m % MOD, m % MOD)
	for i in range(1, x):
		ml[i] = ml[i - 1] * (n + 1)
		ml[i] = ml[i] % MOD
		d = MMI(n + 1 - m, MOD)
		ml[i] = ml[i] * d
		ml[i] = ml[i] % MOD
		n += 1
	ml = ml[::-1]
	for i in range(x):
		su = su + ml[i] * ls[i] % MOD
		su = su % MOD
	print(su)