Кролик Брайан любит шахматы. Недавно он поспорил с кроликом Стьюи что конь лучше короля. Для этого он пытается показать, что конь очень быстрый, но Стьюи не принимает утверждений без доказательств. Он соорудил для Брайана бесконечную шахматную доску, в которой удалил некоторые клетки для спортивного интереса. Брайану осталось посчитать, сколько различных клеток доски достижимы не более чем за k ходов для коня, который стоит в клетке с координатами (0, 0), Естественно, на вырезанные клетки ходить нельзя.
Брайан сам не очень любит точные науки и не знаком с программированием, поэтому вряд ли ему удастся опередить Стьюи, который уже принялся за решение поставленной задачи. Помогите Брайану решить задачку быстрей Стьюи.
Выходные данные
В единственной строке требуется вывести ответ. Так как он может быть достаточно большим нужно вывести его по модулю 1000000007.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 0
|
9
|
|
2
|
2 7
-1 2
1 2
2 1
2 -1
1 -2
-1 -2
-2 -1
|
9
|