Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Туристический маршрут

(Время: 2 сек. Память: 256 Мб Сложность: 88%)

Школьники приехали на экскурсию в новый город и решили осмотреть его достопримечательности. Представим город в виде прямоугольной сетки n × m, в некоторых клетках которой могут находиться достопримечательности.

Друзья начинают свой путь в клетке (1, 1), они хотят дойти до клетки (n, m), а затем вернуться обратно. В городе есть k достопримечательностей, они расположены в клетках (x1, y1), ..., (xk, yk), друзья обязательно хотят посетить их все.

За одну минуту можно перейти из клетки (a, b) в клетку (c, d), если они являются соседними по стороне, то есть выполняется равенство |a−c|+|b−d| = 1. Легко видеть, что на маршрут необходимо потратить хотя бы 2n + 2m − 4 минут, будем рассматривать только такие маршруты.

Будем называть маршрут интересным, если выполняются следующие условия:

  • для того, чтобы пройти маршрут, друзья потратят ровно 2n + 2m − 4 минут;
  • маршрут проходит через каждую клетку не более одного раза.
  • маршрут проходит через все клетки, которые содержат достопримечательности.

Помогите школьникам понять, сколько существует различных интересных маршрутов. Так как это число может оказаться достаточно большим, то выведите его остаток при делении на 109 + 7.

Входные данные

В первой строке входного файла INPUT.TXT указаны числа n, m и k (3 ≤ n, m ≤ 106, 0 ≤ k ≤ 2 000). В последующих k строках указано по паре чисел xi, yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m), гарантируется, что все пары (xi, yi) различны. То есть для любой пары индексов (i, j) (1 ≤ i < j ≤ k) верно хотя бы одно из двух: xi ≠ xj или yi ≠ yj.

Выходные данные

В выходной файл OUTPUT.TXT выведите единственное число – остаток от деления числа интересных маршрутов на 109 + 7.

Примеры

INPUT.TXTOUTPUT.TXT
13 4 2
2 2
2 3
6
23 4 3
3 1
2 3
1 4
0

Пояснение

Ниже изображены все интересные маршруты для первого теста.


Клетки с достопримечательностями обозначены звездочкой.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 2022 / 2023
 2023 / 2024
 2024 / 2025
 A. Кузнечик 2D
 B. Простоватые числа
 C. Кислотные дожди
 D. Поиск сокровищ
 E. Разность квадратов
 F. Перекошенное разбиение
 G. Главное правило личных олимпиад
 H. Туристический маршрут

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru