E. Шахматы
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Кролик Брайан любит шахматы. Недавно он поспорил с кроликом Стьюи что конь лучше короля. Для этого он пытается показать, что конь очень быстрый, но Стьюи не принимает утверждений без доказательств. Он соорудил для Брайана бесконечную шахматную доску, в которой удалил некоторые клетки для спортивного интереса. Брайану осталось посчитать, сколько различных клеток доски достижимы не более чем за 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