Трёхсторонняя ветвь
Дана сетка размером W×H ячеек. Верхняя левая ячейка имеет координаты (1, 1). Вы начинаете движение из ячейки (1, 1) и должны добраться до ячейки (W, H). Разрешено перемещаться только в соседние ячейки: вниз влево, вниз или вниз вправо.
Некоторые ячейки содержат препятствия, на которые перемещаться нельзя. Также нельзя выходить за пределы сетки. Напишите программу, которая вычисляет количество способов добраться до ячейки (W, H) по модулю 1000000009. Гарантируется, что в ячейке (1, 1) препятствий нет.
Входные данные
Первая строка содержит три целых числа: ширину W, высоту H и количество препятствий N. (1 ≤ W ≤ 75, 2 ≤ H ≤ 10^18, 0 ≤ N ≤ 30) Каждая из следующих N строк содержит по 2 целых числа, указывающих координаты препятствия (x_i, y_i).
Последний тестовый случай заканчивается строкой, содержащей три нуля.
Выходные данные
Для каждого тестового случая выведите номер случая и количество способов добраться до ячейки (W, H) по модулю 1000000009.