Купіть Свій Дім
Ви плануєте придбати будинок і звернулися до агентства нерухомості, яке щойно розпочало свою діяльність, і ви станете їхнім першим клієнтом. Тому вони пропонують вам щось особливе.
Агентство має прямокутну ділянку землі з шириною 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.