2. И снова гири
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Составляя тесты к предыдущей задаче, жюри задумалось над вопросом: а сколько различных тестов для заданного $$$k$$$ можно придумать? Жюри считает два теста различными, если один из них нельзя получить из другого обменом групп местами и/или перестановкой чисел в группах. Напишите программу для поиска ответа на этот вопрос.

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

Вводится одно целое число $$$k$$$ ($$$1 \le k \le 16$$$).

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

Выведите одно целое число — количество способов разбить первые $$$4 \cdot k$$$ натуральных чисел на две группы по $$$2 \cdot k$$$ чисел в каждой так, чтобы суммы чисел в группах были одинаковы.

Пример
Входные данные
2
Выходные данные
4
Примечание

В примере для $$$k=2$$$ можно получить 4 различных способа разбиения:

  • 1 2 7 8 и 3 4 5 6
  • 1 3 6 8 и 2 4 5 7
  • 1 4 5 8 и 2 3 6 7
  • 1 4 6 7 и 2 3 5 8

Система оценивания. Решения, верно работающие для $$$k \le 6$$$, будут оценены в 50 баллов.

Обратите внимание: ответ может не помещаться в 32-битный целый тип, рекомендуется использовать 64-битный тип (long long в языке C++, long в Java и C#, int64 в Pascal). В Python ничего дополнительно делать не требуется.