#P3896. 求和

    ID: 3098 传统题 1000ms 512MiB 尝试: 155 已通过: 32 难度: 6 上传者: 标签>CF2000提高差分转化二项式定理组合数乘法递推逆元线性递推

求和

题目描述

给定 TT 个整数 a0,a1,…,aT−1a_0,a_1,\ldots,a_{T-1},令

F(N)=∑i=0N∑k=0T−1akik.F(N)=\sum_{i=0}^{N}\sum_{k=0}^{T-1}a_k i^k.

其中 i0=1i^0=1,包括 i=0i=0 的情形。F(N)F(N) 可以写成关于 NN 的多项式

F(N)=∑k=0TAkNk.F(N)=\sum_{k=0}^{T}A_kN^k.

求各系数 AkA_k 对 109+710^9+7 取模的值。有理系数按分子乘分母的模逆元计算。

输入格式

第一行一个整数 TT。接下来一行依次给出 TT 个整数 a0,a1,…,aT−1a_0,a_1,\ldots,a_{T-1}。

输出格式

输出 T+1T+1 个整数,依次表示 A0,A1,…,ATA_0,A_1,\ldots,A_T 对 109+710^9+7 取模的值。

样例

3
0 0 1
0 166666668 500000004 333333336

数据范围

1≤T≤20001\le T\le2000,0≤ak<109+70\le a_k<10^9+7。

原题公式图