UAIC Competitive Programming

Problem 69: Polynomial Multiplication using FFT

Problem Statement: Given two polynomials represented by their coefficients, compute the product polynomial using Fast Fourier Transform (FFT) and output the coefficients modulo 10^9+7.

Input

The first line contains an integer n denoting the degree of the first polynomial, followed by n+1 coefficients. The next line contains an integer m and m+1 coefficients for the second polynomial.

Output

Print the coefficients of the product polynomial modulo 10^9+7.

Examples


Input:
2
1 2 3
2
4 5 6

Output:
4 13 28 27 18
                

Solution Explanation

Implement FFT to perform polynomial multiplication in O((n+m) log(n+m)) time. Handle modulo arithmetic carefully, possibly using number theoretic transform.

Solution in C++


                    [ a solution will be implemented when possible];
}