Function convolution 

pub fn convolution<M>(
    a: &[StaticModInt<M>],
    b: &[StaticModInt<M>],
) -> Vec<StaticModInt<M>>
where
    M: Modulus,

Calculates the $(+, \times)$ convolution in $\mathbb{Z}/p\mathbb{Z}$.

See the module-level documentation for more details.

Returns a empty Vec if a or b is empty.

Constraints

• $2 \leq m \leq 2 \times 10^9$
• $m$ is a prime number.
• $\exists c \text{ s.t. } 2^c \mid (m - 1), |a| + |b| - 1 \leq 2^c$

where $m$ is M::VALUE.

Complexity

• $O(n \log n + \log m)$ where $n = |a| + |b|$.

Example

use ac_library::ModInt1000000007 as Mint;
use proconio::{input, source::once::OnceSource};

input! {
    from OnceSource::from(
        "3\n\
         1 2 3\n\
         3\n\
         -1 -2 -3\n",
    ),
    a: [Mint],
    b: [Mint],
}

assert_eq!(
    ac_library::convolution(&a, &b),
    [
        Mint::new(-1),
        Mint::new(-4),
        Mint::new(-10),
        Mint::new(-12),
        Mint::new(-9),
    ],
);