BZPRO
#5428. K阶求和数列
内存限制：128 MiB
时间限制：30 Sec
提交
提交记录
讨论
题目描述
对于一个序列A，S1为A一阶求和序列，即S1n=∑Ai(1<=i<=n) ，S1的一阶求和序列S2则为A的二阶求和序列……以此类推SK为A的K阶求和序列。现在要实现以下两个操作：
C L R D：在A序列的[L,R]位置所有数同时加上D。
Q L R：询问SK序列的[L,R]位置所有数的和对10^9+7取模的结果。
输入格式
第一行是三个正整数N，M，K。其中N表示序列的长度、M表示操作次数、K表示询问的序列是SK。
接下来M行，每行代表一个操作，格式如题目描述。
初始A序列中所有数都为0，序列从1开始标号：A1，A2，A3 ......。
N<=200000,M<=200000,k<=10
输出格式
对于每一个询问输出一行一个整数表示答案对10^9+7取模的结果。
样例
样例输入
5 5 1
Q 1 5
C 2 3 1
Q 1 5
C 4 5 2
Q 2 5
样例输出
0
7
13
数据范围与提示
BZPRO