Конфігурації
У цій задачі вам надано сітку розміром RxC (1 ≤ R ≤ 10^9 і 1 ≤ C ≤ 10). У сітці розміщено B блоків (1 ≤ B ≤ 100). Кожен блок займає одну комірку, причому в одній комірці може бути більше одного блоку.
Вам також надано M однакових жетонів, які ви можете розмістити в першому рядку сітки на свій розсуд. У кожній комірці може бути лише один жетон, і ви не можете розміщувати жетони в комірках, зайнятих блоками. Після розміщення жетонів ви можете їх переміщувати, дотримуючись таких правил:
Якщо жетон знаходиться в комірці (r, c), його можна перемістити в (r+1, c-1) або в (r+1, c+1).
Жетон не можна перемістити в комірку, зайняту блоками.
Жетон не можна перемістити за межі сітки.
У кожній комірці може бути лише один жетон.
Всі жетони повинні бути переміщені в i-й рядок, перш ніж будь-який жетон може бути переміщений в (i + 1)-й рядок.
Нехай S = {(1, c_1), (1, c_2), ..., (1, c_M)) — множина комірок, де ви розмістили M жетонів. W(S) — це кількість способів переміщення цих жетонів до останнього рядка. Вам потрібно знайти суму W для всіх можливих S.
Для R = 2, C = 2, M = 1 і B = 0 відповідь дорівнює 2.
Вхідні дані
Перша строка містить кількість тестових випадків 1 ≤ T ≤ 500. Для кожного тестового випадку перша строка містить 1 ≤ R ≤ 10^9, 1 ≤ C ≤ 10 і 0 ≤ M ≤ C. Друга строка містить 0 ≤ B ≤ 100, за якою йдуть B строк, кожна з яких містить два цілі числа r і c (1 ≤ r ≤ R і 1 ≤ c ≤ C), що вказують на позицію комірки кожного блоку.
Вихідні дані
Для кожного тестового випадку ви повинні вивести відповідь в одному рядку, як показано в прикладі виходу. Оскільки відповідь може бути дуже великою, ви повинні взяти модуль від відповіді з 12345.