#arc110d. [arc110_d]Binomial Coefficient is Fun
[arc110_d]Binomial Coefficient is Fun
题目描述
我们有一个包含 个非负整数的序列 。
对于所有长度为 且和不超过 的非负整数序列 ,求 之和, 对 取模。
数据范围
输入格式
第一行输入两个整 ,第二行 个整数,表示序列 。
输出格式
一行,表示答案对 取模的值。
样例解释1
有四个序列 满足 至少为 :
- $B = \{1, 2, 1\}, \prod_{i = 1}^N{B_i \choose A_i} = {1 \choose 1} \times {2 \choose 2} \times {1 \choose 1} = 1$;
- $B = \{2, 2, 1\}, \prod_{i = 1}^N{B_i \choose A_i} = {2 \choose 1} \times {2 \choose 2} \times {1 \choose 1} = 2$;
- $B = \{1, 3, 1\}, \prod_{i = 1}^N{B_i \choose A_i} = {1 \choose 1} \times {3 \choose 2} \times {1 \choose 1} = 3$;
- $B = \{1, 2, 2\}, \prod_{i = 1}^N{B_i \choose A_i} = {1 \choose 1} \times {2 \choose 2} \times {2 \choose 1} = 2$.
它们的答案之和为 。