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];
}