Emma is really fond of integers and loves playing with them. Her friends were jealous, and to test her, one of them gave her a problem. 

Emma is given a list ${A}$ of $N$ integers and is asked a set of ${Q}$ queries. Each query is denoted by an integer ${K}$, for which you have to return the sum of product of all possible sublists having exactly ${K}$ elements. 

Emma has got stuck in this problem and you being her best friend have decided to help her write a code to solve it. Since the answers can be very large, print the answers modulo ${100003}$.

Input Format 

First line has an integer $N$, denoting the number of integers in list ${A}$. Next line contains $N$ space separated integers. The third line contains integer ${Q}$, and next ${Q}$ lines have a single integer ${K}$.

Output Format 

For each of the queries, print the corresponding answer in a new line.  

NOTE Sublist here refers to selecting ${K}$ elements from a list of $N$ elements. There will be $\left(\begin{matrix}N\\ K\end{matrix}\right)$ ways to do that, it doesn't matter if two elements are same.

Constraints 

$1\leq N\leq3\times10^4$ 

$1\leq A_i\leq10^5$ 

$1\leq Q\leq N$ 

$1\leq K\leq N$  

Sample Input #00  

3
1 2 3
2
1
2

Sample Output #00  

6
11

Sample Input #01  

3
1 2 2
1
2

Sample Output #01  

8

Explanation  

Sample #00: 

For $K=1$ possible sublists are $\{1\},\{2\},\{3\}$ so answer is $1+2+3=6$. 

For $K=2$ possible sublists are $\{1,2\},\{2,3\},\{3,1\}$ so answer is $(1\times2)+(2\times3)+(3\times1)=2+6+3=11$.

Sample #01: 

For $K=2$ possible sublists are $\{1,2\},\{2,2\},\{2,1\}$ so answer is $(1\times2)+(2\times2)+(2\times1)=2+4+2=8$.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Matrices


Solutions:
import os, sys, math

def amax(a):
	return max(map(abs, a))

def multiply_polynomials_kronecker_2(p1, p2, modulus):
	(c1max, c2max) = (amax(p1), amax(p2))
	cbound = c1max * c2max * len(p1) * len(p2)
	xlen = int.bit_length(cbound) + 2
	x = 1 << xlen
	x1 = x - 1

	def k(p):
		(t, s) = (1, 0)
		for c in p:
			s += t * c
			t <<= xlen
		return s
	(n1, n2) = (k(p1), k(p2))
	nprod = n1 * n2
	nstr = '{:b}'.format(nprod)[::-1]
	res = []
	for i in range(0, len(nstr), xlen):
		res.append(int(nstr[i:i + xlen][::-1], 2) % modulus)
	return res

def multiply_polynomials_kronecker(ps, modulus):
	if len(ps) == 1:
		return ps[0]
	isplit = len(ps) // 2
	p1 = multiply_polynomials_kronecker(ps[:isplit], modulus)
	p2 = multiply_polynomials_kronecker(ps[isplit:], modulus)
	return multiply_polynomials_kronecker_2(p1, p2, modulus)

def school_multiply(p, q):
	a = [0] * (len(p) + len(q) - 1)
	for (i, x) in enumerate(p):
		for (j, y) in enumerate(q):
			a[i + j] += p[i] * q[j]
	return a

def school_multiply_1cx(c1s, modulus, minDegree=None):
	deg = len(c1s)
	p = [0] * (deg + 1)
	(p[0], p[1]) = (1, c1s[0] % modulus)
	for c in c1s[1:]:
		t = p[0]
		for i in range(1, deg + 1):
			(t, p[i]) = (p[i], (p[i] + c * t) % modulus)
	if minDegree is not None:
		if len(p) < minDegree:
			p += [0] * (minDegree - len(p))
	return p

def mod_vec_add(a, b, m):
	return [(x + y) % m for (x, y) in zip(a, b)]

def mod_reduce(m, a):
	if m is None:
		return a
	return [x % m for x in a]

def solve(A, queries):
	MOD = 10 ** 5 + 3
	polys = []
	batchSize = 32
	for i in range(0, len(A), batchSize):
		polys.append(school_multiply_1cx(A[i:i + batchSize], MOD, minDegree=batchSize))
	C = multiply_polynomials_kronecker(polys, MOD)
	return [C[k] for k in queries]
fptr = open(os.environ['OUTPUT_PATH'], 'w') if 'OUTPUT_PATH' in os.environ else sys.stdout
A_count = int(input())
A = list(map(int, input().rstrip().split()))
queries_count = int(input())
queries = []
for _ in range(queries_count):
	queries_item = int(input())
	queries.append(queries_item)
result = solve(A, queries)
fptr.write('\n'.join(map(str, result)))
fptr.write('\n')
if fptr != sys.stdout:
	fptr.close()


import os, sys, math

def amax(a):
	return max(map(abs, a))

def multiply_polynomials_kronecker_2(p1, p2, modulus):
	(c1max, c2max) = (amax(p1), amax(p2))
	cbound = c1max * c2max * len(p1) * len(p2)
	xlen = int.bit_length(cbound) + 2
	x = 1 << xlen
	x1 = x - 1

	def k(p):
		(t, s) = (1, 0)
		for c in p:
			s += t * c
			t <<= xlen
		return s
	(n1, n2) = (k(p1), k(p2))
	nprod = n1 * n2
	nstr = '{:b}'.format(nprod)[::-1]
	res = []
	for i in range(0, len(nstr), xlen):
		res.append(int(nstr[i:i + xlen][::-1], 2) % modulus)
	return res

def multiply_polynomials_kronecker(ps, modulus):
	if len(ps) == 1:
		return ps[0]
	isplit = len(ps) // 2
	p1 = multiply_polynomials_kronecker(ps[:isplit], modulus)
	p2 = multiply_polynomials_kronecker(ps[isplit:], modulus)
	return multiply_polynomials_kronecker_2(p1, p2, modulus)

def school_multiply(p, q):
	a = [0] * (len(p) + len(q) - 1)
	for (i, x) in enumerate(p):
		for (j, y) in enumerate(q):
			a[i + j] += p[i] * q[j]
	return a

def school_multiply_1cx(c1s, modulus, minDegree=None):
	deg = len(c1s)
	p = [0] * (deg + 1)
	(p[0], p[1]) = (1, c1s[0] % modulus)
	for c in c1s[1:]:
		t = p[0]
		for i in range(1, deg + 1):
			(t, p[i]) = (p[i], (p[i] + c * t) % modulus)
	if minDegree is not None:
		if len(p) < minDegree:
			p += [0] * (minDegree - len(p))
	return p

def mod_vec_add(a, b, m):
	return [(x + y) % m for (x, y) in zip(a, b)]

def mod_reduce(m, a):
	if m is None:
		return a
	return [x % m for x in a]

def solve(A, queries):
	MOD = 10 ** 5 + 3
	polys = []
	batchSize = 32
	for i in range(0, len(A), batchSize):
		polys.append(school_multiply_1cx(A[i:i + batchSize], MOD, minDegree=batchSize))
	C = multiply_polynomials_kronecker(polys, MOD)
	return [C[k] for k in queries]
fptr = open(os.environ['OUTPUT_PATH'], 'w') if 'OUTPUT_PATH' in os.environ else sys.stdout
A_count = int(input())
A = list(map(int, input().rstrip().split()))
queries_count = int(input())
queries = []
for _ in range(queries_count):
	queries_item = int(input())
	queries.append(queries_item)
result = solve(A, queries)
fptr.write('\n'.join(map(str, result)))
fptr.write('\n')
if fptr != sys.stdout:
	fptr.close()


import os, sys, math

def amax(a):
	return max(map(abs, a))

def multiply_polynomials_kronecker_2(p1, p2, modulus):
	(c1max, c2max) = (amax(p1), amax(p2))
	cbound = c1max * c2max * len(p1) * len(p2)
	xlen = int.bit_length(cbound) + 2
	x = 1 << xlen
	x1 = x - 1

	def k(p):
		(t, s) = (1, 0)
		for c in p:
			s += t * c
			t <<= xlen
		return s
	(n1, n2) = (k(p1), k(p2))
	nprod = n1 * n2
	nstr = '{:b}'.format(nprod)[::-1]
	res = []
	for i in range(0, len(nstr), xlen):
		res.append(int(nstr[i:i + xlen][::-1], 2) % modulus)
	return res

def multiply_polynomials_kronecker(ps, modulus):
	if len(ps) == 1:
		return ps[0]
	isplit = len(ps) // 2
	p1 = multiply_polynomials_kronecker(ps[:isplit], modulus)
	p2 = multiply_polynomials_kronecker(ps[isplit:], modulus)
	return multiply_polynomials_kronecker_2(p1, p2, modulus)

def school_multiply(p, q):
	a = [0] * (len(p) + len(q) - 1)
	for (i, x) in enumerate(p):
		for (j, y) in enumerate(q):
			a[i + j] += p[i] * q[j]
	return a

def school_multiply_1cx(c1s, modulus, minDegree=None):
	deg = len(c1s)
	p = [0] * (deg + 1)
	(p[0], p[1]) = (1, c1s[0] % modulus)
	for c in c1s[1:]:
		t = p[0]
		for i in range(1, deg + 1):
			(t, p[i]) = (p[i], (p[i] + c * t) % modulus)
	if minDegree is not None:
		if len(p) < minDegree:
			p += [0] * (minDegree - len(p))
	return p

def mod_vec_add(a, b, m):
	return [(x + y) % m for (x, y) in zip(a, b)]

def mod_reduce(m, a):
	if m is None:
		return a
	return [x % m for x in a]

def solve(A, queries):
	MOD = 10 ** 5 + 3
	polys = []
	batchSize = 32
	for i in range(0, len(A), batchSize):
		polys.append(school_multiply_1cx(A[i:i + batchSize], MOD, minDegree=batchSize))
	C = multiply_polynomials_kronecker(polys, MOD)
	return [C[k] for k in queries]
fptr = open(os.environ['OUTPUT_PATH'], 'w') if 'OUTPUT_PATH' in os.environ else sys.stdout
A_count = int(input())
A = list(map(int, input().rstrip().split()))
queries_count = int(input())
queries = []
for _ in range(queries_count):
	queries_item = int(input())
	queries.append(queries_item)
result = solve(A, queries)
fptr.write('\n'.join(map(str, result)))
fptr.write('\n')
if fptr != sys.stdout:
	fptr.close()