Joker and the Arkham Asylum

All submissions for this problem are available.
The Arkham Asylum of Gotham, is the place of residence of evils. Batman uses his super awesome BatTechnology to guard it against the potential outbreak.
The Asylum can be considered as a NxN maze, where each cell houses a building. Note that, the left most building in the bottom most row is said to be present at the cell in 1^{st} row and 1^{st} column. Similarly, the right most building in the top most row is said to be present at the cell in N^{th} row and N^{th} column. Each building is pyramidal in shape and is three storey high.
Once a while, Batman catches prisoners and puts them into Arkham Asylum. Note that, initially, the Asylum is empty. For proper utilization of pyramidal space, the distribution of new prisoners in a building is as follows:
If D+D^{2}+D^{3} new prisoners are inserted in a building, D^{3} goes into ground floor, D^{2} into first floor and D into second floor.
Now, Batman places the new prisoners in the buildings along a tilted line, 45° to the sides of the maze, in the increasing direction of row numbers.
Note that, he could start this line anywhere in the first row. He would place (D+D^{2}+D^{3}) prisoners in each building, in above described manner.Also, it is guaranteed that the number of new prisoners would be a multiple of D+D^{2}+D^{3} and this line would atmost reach the boundary of the maze, i.e Batman would start this line well in advance, so as to accommodate all prisoners.
Under the effect of the super awesome BatTechnology, the power packets required to escape from the Asylum, for each prisoner living in the building at j^{th} row and
i^{th} column of the maze is given by:
 F_{0} (i,j) = (j1)^{3} for the ground floor
 F_{1} (i,j) = (j1)^{2} for the first floor
 F_{2} (i,j) = (j1) for the second floor
Note that the super awesome BatTechnology is supercostly (even for Batman!) and is employed just inside the Asylum and nowhere else outside it. So, the prisoners are free to move anywhere once they are outside the prison.
Now the Joker, who enjoys chaos, decides to free some prisoners. For that, he needs some power packets, which he can smuggle into the Asylum and distribute it amongst prisoners so as they can be free and join with him in his quest for establishing the reign of Chaos in the universe.
The Joker needs your help to find out the number of power packets needed to free the prisoners from all the building in between and including columns X and Y, in all rows. Since the answer could be very, very large (after all, you are fighting against the super awesome BatTechnology), you need to print your answer modulus 10^{9}+7.
Input Format
 First Line contains 2 space separated Integers N and T, denoting the size of the maze and the number of queries to follow.
 Next T lines follow which will either be of form (U X Y D) OR (Q X Y) without brackets.
U X Y D denotes the addition of (YX+1)*(D+D^{2}+D^{3}) prisoners, in a line starting from the X^{th} building in first row and extending upto Y^{th} building in (YX+1)^{th} row,
Q X Y denotes that Joker wishes to query the cost of releasing the prisoners in the above described manner.
Output Format
 For each Query of type Q output a single line containing the answer as required.
Constraints
 1 ≤ N ≤ 10^{5}
 1 ≤ T ≤ 10^{5}
 1 ≤ X ≤ Y ≤ N
 1 ≤ D ≤ 100
Sample Input
4 2
U 1 4 2
Q 2 3
Sample Output
98
Explanation
After the first update, the Asylum looks like this:
0,0,0 0,0,0 0,0,0 8,4,2
0,0,0 0,0,0 8,4,2 0,0,0
0,0,0 8,4,2 0,0,0 0,0,0
8,4,2 0,0,0 0,0,0 0,0,0
Here, each tuple (a,b,c) denotes the current number of persons in the building, in ground floor, first floor and second floor respectively.
The answer is (8*1+4*1+2*1)+(8*8+4*4+2*2) = 14+84 = 98
Author:  iopc_admin 
Tags  iopc_admin 
Date Added:  2022014 
Time Limit:  2  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, GO 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 