z-product
Mr. Little Z got an N x N matrix of integers. At the beginning all the values of the matrix are set to 1.
Matrix supports two types of operation:
- 1 x y v - set value of cell (x,y) to v , ( 1 <= x, y <= N ), ( 1 <= v <= 10000 )
- 2 x1 y1 x2 y2 - print the product of the values in the rectangle from (x1, y1) to (x2, y2), inclusive. ( 1 <= x1 <= x2 <= N ), ( 1 <= y1 <= y2 <= N ).
Little Z wants to check the correctness of matrix operations and asks you to simulate the work of matrix through Q given operations of types 1 and 2.
InputIn the first line of the standard input there are 2 space separated integers N ( 1 <= N <= 1000 ) and Q ( 1 <= Q <= 60000 ).
In the next Q lines there are Q queries formatted as described above.
In the next Q lines there are Q queries formatted as described above.
OutputFor every operation of the type 2, to the standard output print one line with the answer for this query. As this number can be very big print it with modulo 10007.
Input:
Output:
2 4
2 1 1 2 2
2 1 2 2 2
1 2 2 3
2 2 1 2 2Output:
1
1
3 Input:
Output:
4 14
1 1 1 123
1 2 3 224
2 1 2 3 3
2 1 1 4 4
1 2 4 197
2 3 4 3 4
2 1 1 2 2
2 1 2 1 3
1 1 2 564
1 3 3 12
2 2 2 3 4
2 2 1 4 3
1 1 2 37
2 1 1 4 4Output:
224
7538
1
123
1
9172
2688
2575Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.