Ваші Шляхи#5701

Ваші Шляхи

1 секунда

256 мегабайтів

Дуже складна

Ви живете в невеликому, добре спланованому прямокутному місті на Пхукеті. Розмір центральної частини міста становить $H$ кілометрів $\times$ $W$ кілометрів. Центральна частина поділена на $H W$ одиничних блоків, кожен розміром $1 \times 1$ 1 \times 1 км². Є $H + 1$ H+1 вулиць, що йдуть із заходу на схід, і $W + 1$ W+1 проспектів, що йдуть з півночі на південь. Центральну частину можна уявити як прямокутник на площині, як показано нижче.

Рисунок 1. Центральна частина міста, де $H = 3$ H = 3, а $W = 6$ W = 6.

Ми можемо ідентифікувати кожне перехрестя за його координатами на площині. Наприклад, на рисунку вище лівий нижній кут — це перехрестя $(0, 0)$ , а правий верхній кут — це перехрестя $(6, 3)$ .

Ваш дім знаходиться в лівому нижньому куті (тобто, перехрестя $(0, 0)$ ) і ви хочете дістатися до університету у правому верхньому куті (тобто, перехрестя $(W, H)$ (W, H)). Більше того, ви хочете дістатися до університету без зайвих зусиль; тому ви хочете йти тільки з заходу на схід і з півдня на північ. Таким чином, у прикладі вище є $84$ способи дістатися до університету.

Ви плануєте ходити до університету протягом $K$ днів. Ситуація ускладнюється тим, що щоранку місто блокує частини вулиць і проспектів для прибирання. Блокування здійснюється таким чином, що неможливо дістатися до частин вулиць або проспектів, які заблоковані, з інших частин, які також заблоковані, через будь-які шляхи, що містять лише рухи з заходу на схід і з півдня на північ.

Ви все ще хочете дістатися до університету, використовуючи ту ж стратегію з заходу на схід і з півдня на північ. Ви хочете дізнатися для кожного дня, скільки способів ви можете дістатися до університету, йдучи тільки з заходу на схід і з півдня на північ. Оскільки число може бути дуже великим, ми хочемо лише результат за модулем $2552$ .

Вхідні дані

Перший рядок містить ціле число $T$ , кількість тестових випадків ( $1 \leq T \leq 5$ 1 \leq T \leq 5). Кожен тестовий випадок має наступний формат.

Перший рядок кожного тестового випадку містить $3$ цілі числа: $W$ , $H$ та $K$ ( $1 \leq W \leq 1000$ 1 \leq W \leq 1000, $1 \leq H \leq 1000$ 1 \leq H \leq 1000, $1 \leq K \leq 10000$ 1 \leq K \leq 10000). $W$ і $H$ визначають розмір центральної частини. $K$ позначає кількість днів, коли ви хочете дістатися до університету.

Наступні $K$ рядків описують інформацію про заблоковані частини вулиць і проспектів. Більш конкретно, рядок $1 + i$ 1+i, для $1 \leq i \leq K$ 1 \leq i \leq K, починається з цілого числа $Q_{i}$ Q_i ( $1 \leq Q_{i} \leq 100$ 1 \leq Q_i \leq 100), що позначає кількість частин, які заблоковані. Потім слідують $Q_{i}$ Q_i наборів з $4$ цілих чисел, що описують заблоковані частини. Кожна частина описується $4$ цілими числами, $A$ , $B$ , $C$ і $D$ ( $0 \leq A \leq C \leq W$ 0 \leq A \leq C \leq W, $0 \leq B \leq D \leq H$ 0 \leq B \leq D \leq H), що означає, що частини, що з'єднують перехрестя $(A, B)$ і $(C, D)$ (C, D), заблоковані. Гарантується, що ця частина є дійсною частиною вулиць або проспектів, також $C - A \leq 1$ C-A \leq 1, і $D - B \leq 1$ D-B \leq 1, тобто частина має довжину $1$ км.

Вихідні дані

Для кожного тестового випадку, для кожного дня, ваша програма повинна вивести кількість способів дістатися до університету за модулем $2552$ в окремому рядку. Тобто, вихідні дані для кожного тестового випадку повинні містити $K$ рядків.

Приклади

Приклад 1