3944: 二项卷积
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
这是一道模板题。
给数列 $a_0, \dots, a_n, b_0, \dots, b_m$ 和正整数 $M$，求数列 $c_0, \dots, c_{n+m}$，满足：
$$
c_k = \sum_{i=\max(k-m,0)}^{\min(k,n)} \binom k i a_i b_{k-i} \bmod M
$$
其中 $\binom k i = \frac{k!}{i!(k-i)!}$ 是组合数。
输入
第一行输入三个正整数 $n, m, M$。
接下来一行输入 $n + 1$ 个整数 $a_0, \dots, a_n$。
接下来一行输入 $m + 1$ 个整数 $b_0, \dots, b_m$。
输出
输出一行 $n + m + 1$ 个数，依次输出 $c_0, c_1, \dots, c_{n+m}$。
样例输入 复制
2 5 114
5 1 4
1 9 1 9 8 10样例输出 复制
5 46 27 42 100 108 84 42提示
数据范围：对于 $10\%$ 的数据，保证 $n,m\le 10^3$。 对于另外 $20\%$ 的数据，保证 $M$ 是质数。 对于另外 $20\%$ 的数据，保证 $M$ 是 $2$ 的幂。 对于 $100\%$ 的数据，保证 $0\le n, m\le 10^5, 2\le M\le 10^9, 0\le a_i, b_j < M$。