The Massey Green club has gone out into the field to plant trees (for bonus marks, of course). The field is a grid with the top-left square labelled ~(1,1)~. The square ~(x,y)~ would be located ~x-1~ units to the right of ~(1,1)~ and ~y-1~ units below ~(1,1)~. The grid is infinitely long in the positive ~x~ and ~y~ axes. The Massey Green club can perform 2 operations:

1. Plant ~t~ ~(1 \le t \le 10\,000)~ trees at position ~(r,c)~. It is guaranteed that the Manhattan distance of square ~(r,c)~ from square ~(1,1)~ will be less than or equal to ~2\,000~ and that ~r,c~ are positive integers.

2. Find the number of trees on all squares on the diagonal from squares ~(r,c)~ to ~(r-x,c+x)~. It is guaranteed that the Manhattan distance of ~(r,c)~ from square ~(1,1)~ will be less than or equal to ~2\,000~, ~0 \le x < r~, and ~r, c, x~ are positive integers.

Input Specification

The first line will contain ~N~ ~(1 \le N \le 400\,000)~, the number of commands you will be given. The next ~N~ lines each contain a command as ~4~ space-separated integers.

The first integer will be either ~1~ or ~2~, for the type of operation you will be asked to perform. If the type is ~1~, the next ~3~ integers are ~r~ ~c~ ~t~ in that order. If the type is ~2~, the next 3 integers are ~r~ ~c~ ~x~ in that order.

Output Specification

Print the sum of the answers to all the type ~2~ operations, modulo ~10^9 + 7~.

Sample Input

5
1 2 3 2
2 4 1 3
1 4 3 4
1 3 2 3
2 4 1 3

Sample Output

7

Explanation for Sample Output

The first command places 2 trees at the spot ~(2,3)~. The second command asks you to count the trees between ~(4,1)~ and ~(1,4)~, as marked by the "X"s on the grid. The 2 trees from the first command fall in this area, therefore the answer is ~2~. For the last command, the trees from the first and the third commands fall in the range, therefore the result is ~5~. You should print ~2+5 = 7~.

	1	2	3	4	5	6
1				X
2			3
3		2		4
4	X
5
6

---