#97. Binomial Convolution

    ID: 97 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>模板DFT(含 NTT)及FFT数论中国剩余定理

Binomial Convolution

当前没有测试数据。

Description

Given two sequences a0,,an,b0,,bma_0, \dots, a_n, b_0, \dots, b_m and a positive integer MM. Calculate an integer sequence c0,,cn+mc_0, \dots, c_{n+m}, satisfying:

$$c_k = \sum_{i=\max(k-m,0)}^{\min(k,n)} \binom k i a_i b_{k-i} \bmod M $$

Here (ki)=k!i!(ki)!\binom k i = \frac{k!}{i!(k-i)!} denotes the binomial coefficient.

Input Format

The first line consists of integer n,m,Mn, m, M.

The second line consists of a0,,ana_0,\dots,a_n.

The third line consists of b0,,bmb_0,\dots,b_m.

Output Format

Print one line, containing c0,,cn+mc_0,\dots,c_{n+m}.

Example

2 5 114
5 1 4
1 9 1 9 8 10
5 46 27 42 100 108 84 42

The sequence is [5,46,27,156,100,450,540,840][5, 46, 27, 156, 100, 450, 540, 840] before modulo.

Limits

For 10%10\% of the test cases, it's guaranteed that n,m103n,m\le 10^3.

For another 20%20\%, MM is a prime.

For another 20%20\%, MM is a power of 22.

For 100%100\% of the test cases, it's guaranteed that $0\le n, m\le 10^5, 2\le M\le 10^9, 0\le a_i, b_j < M$.