The MacFax Donut Cafe is expanding its restaurants into Canada. To kickstart their operations, they decided to open up a restaurant on every intersection along Yonge Street. Yonge Street is one of the longest streets in the world, and is composed of ~N~ intersections, beginning at Toronto's lakeshore with index ~1~ and ending near Lake Simcoe with index ~N~. To simplify, each restaurant will be numbered the same as the intersection they are on. The company wants to celebrate their openings with a series of promotions, which they will announce on live television, each promotion consists of one of two events:
- Add ~1^k,2^k,3^k\ldots(r-l+1)^k~ free donut coupons to the stores ~l,l+1,l+2\ldots r~ in that order.
- Ask the audience to count the total number of coupons that have been placed in the stores ~l,l+1,l+2\ldots r~ modulo ~10^9+7~.
Since none of the other eager customers realize that they can use a computer program to find the answer, you try to code your program quickly before the game starts so you can win all the prizes.
For all subtasks:
~1 \leq N, Q \leq 10^5~
~0 \leq K^5 \leq 10^5~
~1 \leq l \leq r \leq N~
|4||No additional constraints||55|
The first line will contain ~N~ and ~Q~.
~Q~ lines of input follow in one of the following formats:
U l r kAdd free donut coupons to the stores ~l,l+1,l+2\ldots r~ as described above.
Q l rFind the total number of free donut coupons added to the stores ~l,l+1,l+2\ldots r~ modulo ~10^9+7~.
Q type query, print the answer modulo ~10^9+7~ on a new line.
Sample Input 1
6 6 U 4 6 0 Q 4 5 U 1 4 1 Q 1 4 U 1 4 2 Q 4 4
Sample Output 1
2 11 21
Sample Explanation 1
The various stages of updates:
Sample Input 2
10 11 U 1 10 5 Q 1 1 Q 2 2 Q 3 3 Q 4 4 Q 5 5 Q 6 6 Q 7 7 Q 8 8 Q 9 9 Q 10 10
Sample Output 2
1 32 243 1024 3125 7776 16807 32768 59049 100000