Пусть нам дано натуральное число \(N\). Рассмотрим множество различных целых чисел \(\{a_1, a_2, \dots, a_k\}\), где каждое число лежит в интервале от \(0\) до \(N-1\) включительно. Назовём такое множество свободным от сумм, если в этом множестве не найдётся таких трёх чисел, что сумма двух из них сравнима с третьим по модулю \(N\). Строго говоря, назовём множество свободным от сумм, если для каждой тройки (не обязательно различных) индексов \(x\), \(y\) и \(z\) (\(1\leq x,y,z\leq k\)) выполняется неравенство: \(\)(a_x+a_y) \bmod N \neq a_z\(\)

где \(p \bmod q\) — остаток от деления \(p\) на \(q\).

Например, при \(N=6\) множествами, свободными от сумм, не являются, например, \(\{0\}\) (т.к. \((0+0)\bmod 6=0\)), \(\{1,2\}\) (т.к. \((1+1) \bmod 6=2\)), \(\{3,4,5\}\) (т.к. \((4+5)\bmod 6=3\)), но множество \(\{1,3,5\}\) является свободным от сумм.

По заданному \(N\) определите, сколько существует множеств, свободных от сумм.