Конфигурации
В этой задаче вам предстоит работать с сеткой размером 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.