Купите Ваш Дом
Вы собираетесь купить дом и обратились в строительную компанию, которая только начала свою деятельность, и вы станете их первым клиентом. В связи с этим они предлагают вам особые условия.
У компании есть прямоугольный участок земли шириной W и высотой H. Для измерения участка используется система координат, где (0, 0) — это нижний левый угол. Любая точка, находящаяся на расстоянии x от нижнего края и y от левого края, обозначается как (x, y).
На этом участке уже построено несколько домов, все они прямоугольной формы, и их стороны параллельны сторонам участка. Положение дома задается четырьмя целыми числами x_1, y_1, x_2, y_2, где (x_1, y_1) — это нижний левый угол, а (x_2, y_2) — верхний правый угол дома.
Особое предложение заключается в том, что вы можете выбрать любую прямоугольную область, содержащую ровно один дом и любое количество прилегающего открытого пространства. Если у вас недостаточно средств, вы можете выбрать только область, занимаемую домом. Если средств достаточно, можно оставить открытое пространство для сада!
Однако есть некоторые ограничения. Для удобства использования оставшейся земли в будущем вы можете выбрать только прямоугольную область, стороны которой параллельны сторонам участка. Углы выбранной области должны иметь целочисленные координаты, например, (3, 2), но не (3.5, 2). Вы не можете выбрать область, в которой часть дома находится внутри, а часть — снаружи. Вы не можете выбрать область, содержащую более одного дома или не содержащую ни одного дома. Сколько способов выбрать участок, соблюдая эти правила?
Входные данные
Ввод начинается с целого числа T (T около 500), количества тестов. Каждый тест начинается с двух целых чисел W и H (1 ≤ W, H ≤ 1000000000), ширины и высоты участка, и следующая строка содержит целое число N(1 ≤ N ≤ 50), количество домов на участке. Каждая из следующих N строк содержит четыре целых числа x_1, y_1, x_2, y_2 (0 ≤ x_{1 }< x_2 ≤ W и 0 ≤ y_1 < y_2 ≤ H), которые описывают местоположение дома. Обратите внимание, что дома не пересекаются, и все координаты — неотрицательные целые числа.
Выходные данные
Для каждого теста выведите строку в формате "Case #: W", где '#' заменяется на номер теста, а W — на количество способов выбрать участок. Поскольку W может быть очень большим, выведите количество способов по модулю 1000000007.