Два равных множества
Дано положительное целое число
n. Требуется найти, сколькими способами можно разбить числа 1, 2, ..., n на два множества с равными суммами.
Например, если
n = 7, то существует четыре способа разделить числа на два множества с одинаковой суммой
{1, 3, 4, 6} и {2, 5, 7}
{1, 2, 5, 6} и {3, 4, 7}
{1, 2, 4, 7} и {3, 5, 6}
{1, 6, 7} и {2, 3, 4, 5}Вход
В единственной строке дано целое число
n (1 ≤ n ≤ 500).Выход
Выведите ответ по модулю .
Примеры
Ввод | Вывод |
7 | 4 |
10 | 0 |
Constraints
Time limit: 20 seconds
Memory limit: 512 MB
Output limit: 1 MB