seuOJ282 - 数列求和

题目描述

小雅米在隔离时非常无聊，于是他又打起了数列的主意。

小雅米选择了一个数列 fn{f_n} , 数列通项公式可表达为一个多项式：fn=∑i=0mainif_n=\sum_{i=0}^m{a_in^i}。他想知道数列 sn=∑i=1nfis_n=\sum_{i=1}^n f_i 用多项式表示的通项公式，即求表达式 sn=∑i=0m+1binis_n=\sum_{i=0}^{m+1}{b_in^i} 中的系数 b0,b1,...,bm+1b_0,b_1,...,b_{m+1}。

后来小雅米发现求数列的通项公式有点困难，于是他改变了想法，他想知道数列 sns_n 的其中 kk 项。

由于数据可能很大，你仅需要输出结果除 108+7‬10^8+7‬ 后的余数即可。

输入格式

测试数据共 33 行：

第一行 22 个整数 m,k(1≤m≤103，1≤k≤2×103)m,k(1 \leq m \leq 10^3，1 \leq k \leq 2\times 10^3)。

第二行 m+1m+1 个整数 a0,a1,...,am(0≤ai<108+7）a_0,a_1,...,a_m(0 \leq a_i < 10^8+7），表示数列 fnf_n 的系数。

第三行 kk 个整数 p1,p2,...,pk(1≤pi≤106‬)p_1,p_2,...,p_k(1 \leq p_i \leq 10^6‬)，表示小雅米想要求的数列中的其中 kk 项 sp1,sp2,...,spks_{p_1},s_{p_2},...,s_{p_k}。

输出格式

输出一行 kk 个整数为 sp1,sp2,...,spks_{p_1},s_{p_2},...,s_{p_k} 分别除 108+7‬10^8+7‬ 后的余数，用空格隔开。

样例

样例输入

1 2
1 3
1 3

样例输出

4 21

样例解释

例子中 fn=3n+1,sn=32n2+52nf_n=3n+1, s_n=\frac{3}{2}n^2+\frac{5}{2}n。