Question

Пчёлка

Представьте себе пчелиные соты — поле из шестиугольных клеток со стороной, состоящей из NN клеток. В верхней левой клетке AA находится пчёлка. За один ход она может переползти на клетку вниз, на клетку вниз-вправо или на клетку вверх-вправо (вверх и влево пчёлка не ползает).

Требуется написать программу, которая найдёт количество способов, которыми пчёлка может переместиться из клетки AA в противоположную клетку BB по указанным правилам.



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

Единственная строка содержит единственное число NN — размеры шестиугольного поля (2 ≤ N ≤ 12)(2 ≤ N ≤ 12).

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

Выведите единственное целое число — количество способов.

Примеры

Ввод 1

2

Вывод

11

Ввод 2

3

Вывод

291

​

Answer 1

Ответ:

n = int(input())

m = 2 * n - 1

field = [[0] * m for _ in range(m)]

field[0][0] = 1

for x in range(m):

   for y in range(m):

       if m >= y - x + n > 0:

           if x > 0:

               field[y][x] += field[y][x - 1]

           if y > 0:

               field[y][x] += field[y - 1][x]

           if x > 0 and y > 0:

               field[y][x] += field[y - 1][x - 1]

print(field[m - 1][m - 1])