F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:本站提供各级各类比赛备战资源(Noip提高组及以下),有意者请联系Lydsy2012@163.com,仅限教师及家长用户。
Problem 5428. -- K阶求和数列

5428: K阶求和数列

Time Limit: 30 Sec  Memory Limit: 128 MB
Submit: 18  Solved: 9
[Submit][Status][Discuss]

Description

对于一个序列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取模的结果。

Input

第一行是三个正整数N,M,K。其中N表示序列的长度、M表示操作次数、K表示询问的序列是SK。
接下来M行,每行代表一个操作,格式如题目描述。
初始A序列中所有数都为0,序列从1开始标号:A1,A2,A3 ......。
N<=200000,M<=200000,k<=10

Output

对于每一个询问输出一行一个整数表示答案对10^9+7取模的结果。

Sample Input

5 5 1
Q 1 5
C 2 3 1
Q 1 5
C 4 5 2
Q 2 5

Sample Output

0
7
13

HINT

Source

[Submit][Status][Discuss]

HOME Back