Трьохстороння гілка
Є сітка розміром 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.