Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

You are given a polynomial of degree N with integer coefficients. Your task is to find the value of this polynomial at some K different integers, modulo 786433.

------ Input ------ 

The first line of the input contains an integer N denoting the degree of the polynomial.
The following line of each test case contains (N+1) integers denoting the coefficients of the polynomial. The i^{th} numbers in this line denotes the coefficient a_{i-1} in the polynomial a_{0} + a_{1} × x^{1} + a_{2} × x^{2} + ... + a_{N} × x^{N}. 
The following line contains a single integer Q denoting the number of queries.
The j^{th} of the following Q lines contains an integer number x_{j} denoting the query.

------ Output ------ 

For each query, output a single line containing the answer to the corresponding query. In other words, the j^{th} line of the output should have an integer equal to a_{0} + a_{1} × x_{j} + a_{2} × x_{j}^{2} + ... + a_{N} × x_{j}^{N} modulo 786433.

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

$0 ≤ a_{i}, x_{j} < 786433$
$Subtask #1 (37 points): 0 ≤ N, Q ≤ 1000$
$Subtask #2 (63 points): 0 ≤ N, Q ≤ 2.5 × 10^{5}$

------ Example ------ 

Input:
2
1 2 3
3
7
8
9

Output:
162
209
262

------ Explanation ------ 

Example case 1. 

$Query 1: 1 + 2 × 7 + 3 × 7 × 7 = 162$
$Query 2: 1 + 2 × 8 + 3 × 8 × 8 = 209$
$Query 3: 1 + 2 × 9 + 3 × 9 × 9 = 262$

Source: codechef | Difficulty: VERY_HARD
Tags: Polynomials and generating functions

Matrices

Mathematics


Solutions:
(p, r) = (786433, 10)

def DFT(a, w, order):
	if len(a) == 1:
		return [a[0]] * order
	(feven, fodd, res, x, half_order) = (DFT(a[0::2], w * w % p, order // 2), DFT(a[1::2], w * w % p, order // 2), [0] * order, 1, order // 2)
	for i in range(order // 2):
		(res[i], res[i + half_order]) = ((feven[i] + x * fodd[i]) % p, (feven[i] - x * fodd[i]) % p)
		x = x * w % p
	return res

def calcPolynomialValues(a):
	(dft, res, x) = (DFT(a, r, p - 1), [a[0]] + [0] * (p - 1), 1)
	for i in range(p - 1):
		res[x] = dft[i]
		x = x * r % p
	return res
(n, pol_values) = (int(input()), calcPolynomialValues(list(map(int, input().split()))))
for i in range(int(input())):
	print(pol_values[int(input())])