| Russian Code Cup 2016 - Финал [неофициальная интернет-трансляция, рекомендуется для Div. 1] |
|---|
| Закончено |
Девочка Маша очень любит зимние виды спорта, и сегодня ей предстоит пройти лыжный слалом.
Трасса схематически представляет из себя клетчатый прямоугольник n × m. На поле размещены прямоугольные препятствия, занимающие некоторые клетки. Маша должна добраться из клетки с координатами (1, 1), в клетку (n, m). При этом из каждой клетки можно перейти либо на одну клетку вверх, либо на одну клетку вправо. В клетки, в которых расположены препятствия, попадать нельзя.
Таким образом, каждое препятствие можно обойти двумя способами: оно останется либо слева от траектории движения по трассе, либо справа. Маша любит разнообразие, и ей интересно, сколько существует различных способов пройти трассу. Проходы трассы считаются различными, если существует хотя бы одно препятствие, которое в одном проходе находится слева, а в другом справа от траектории Маши.
Ваша задача — помочь Маше узнать количество различных способов пройти трассу. Ответ может быть большим и Машу устроит значение по модулю 109 + 7.
На рисунках ниже разобраны тесты из условия. 
В первой строке входных данных содержатся три натуральных числа n, m и k (3 ≤ n, m ≤ 106, 0 ≤ k ≤ 105) — размеры трассы и количество препятствий соответственно.
В следующих k строках находится по четыре натуральных числа x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m) — координаты левого нижнего и правого верхнего угла препятствия.
Гарантируется, что в клетках (1, 1) и (n, m) нет препятствий, и все препятствия не имеют пересечений (но могут касаться).
В выходной файл выведите единственное число — остаток от деления количества различных способов пройти трассу на число 109 + 7.
3 3 0
1
4 5 1
2 2 3 4
2
5 5 3
2 2 2 3
4 2 5 2
4 4 4 4
3
