На доске размера $$$n \times m$$$ клеток требуется определить количество различных пар клеток, между которыми может переместиться ферзь за один ход и при это не пересекая ни один из заданных прямоугольников. Дополнительно известно, что каждая клетка принадлежит не более одному прямоугольнику. Напомним, что ферзь за один ход может перемещать на любое количество квадратов по прямой линии — по вертикали, по горизонтали или по диагонали.
Так как ответ может быть большим, выведите его по модулю $$$10^9+7$$$.
В первой строке задается три целых числа $$$n$$$ $$$m$$$ $$$k$$$ — размеры поля и количество прямоугольников соотвественно. В следующих $$$k$$$ строках задается по четыре целых числа $$$r1_i$$$ $$$c1_i$$$ $$$r2_i$$$ $$$c2_i$$$ — координаты $$$i$$$-го прямоугольника. Никакие два различных прямоугольника не имеют общую клетку.
$$$$$$ 1 \le n, m \le 10^9 $$$$$$ $$$$$$ 0 \le k \le 10^5 $$$$$$ $$$$$$ 1 \le r1_i \le r2_i \le n $$$$$$ $$$$$$ 1 \le c1_i \le c2_i \le m $$$$$$
В единственной строке выведите количество пар клеток, между которым допустим королевский ход вне прямоугольников, по модулю $$$10^9+7$$$.
1 6 1 1 3 1 3
4
3 3 1 2 2 2 3
11
6 9 5 1 6 4 8 3 2 6 2 2 1 6 1 1 3 5 5 3 9 4 9
42
