Codeforces Beta Round 53 |
---|
Закончено |
Кролик Брайан любит шахматы. Недавно он поспорил с кроликом Стьюи что конь лучше короля. Для этого он пытается показать, что конь очень быстрый, но Стьюи не принимает утверждений без доказательств. Он соорудил для Брайана бесконечную шахматную доску, в которой удалил некоторые клетки для спортивного интереса. Брайану осталось посчитать, сколько различных клеток доски достижимы не более чем за k ходов для коня, который стоит в клетке с координатами (0, 0), Естественно, на вырезанные клетки ходить нельзя.
Брайан сам не очень любит точные науки и не знаком с программированием, поэтому вряд ли ему удастся опередить Стьюи, который уже принялся за решение поставленной задачи. Помогите Брайану решить задачку быстрей Стьюи.
Первая строка содержит два целых числа k и n (0 ≤ k ≤ 1018, 0 ≤ n ≤ 440) — соответственно максимальное количество ходов, которые может совершить конь, и количество удаленных клеток. Далее записано n строк — каждая задает координаты вырезанной клетки в виде (xi, yi) (|xi| ≤ 10, |yi| ≤ 10). Все числа целые, вырезанные клетки различны, и клетка (0, 0) гарантированно не вырезана.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cin (также вы можете использовать спецификатор %I64d).
В единственной строке требуется вывести ответ. Так как он может быть достаточно большим нужно вывести его по модулю 1000000007.
1 0
9
2 7
-1 2
1 2
2 1
2 -1
1 -2
-1 -2
-2 -1
9
Название |
---|