We note that the answer is just the finite discrete linear convolution (or polynomial product) of the input arrays. In order for the solution to be efficient enough, Fast Fourier Transforms must be used.

The intended solution is to perform two Number Theoretic Transforms, modulo two different primes that fit in a 32-bit integer and use the Chinese Remainder Theorem to get the answer modulo a 64-bit integer greater than the maximum possible value. The recursive version of FFT/NTT will likely time out; it is highly recommended to use the iterative version.

Constant optimization may be required. Some possible constant-optimizations include using 128-bit integers and using fast IO. These are not part of the author's official solution.

Time Complexity: ~\mathcal{O}(N \log N)~