Пусть нам дано натуральное число \(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\) определите, сколько существует множеств, свободных от сумм.

У мальчика Васи есть \(N\) шоколадок (возможно, разного веса). Вася пригласил к себе в гости \(K\) своих друзей и хочет подарить им шоколадки. Чтобы никому из друзей не было обидно, Вася решил раздать шоколадки так, чтобы каждому другу досталось одно и то же количество шоколада (т.е. суммарный вес шоколадок, доставшихся каждому другу, должен быть одинаковым). Вася может раздать все свои шоколадки, может раздать лишь часть, но, поскольку он — очень гостеприимный мальчик, он не хочет оставлять друзей совсем без шоколада (т.е. сумма весов шоколадок, доставшихся каждому другу, должна быть строго положительной). Все шоколадки красиво упакованы, т.е. делить их на части нельзя.

Определите, сколько у Васи есть способов раздать шоколад своим друзьям. Два способа считайте различными тогда и только тогда, когда существует шоколадка, которая в одном способе досталась некоторому другу, а в другом — другому другу или вовсе не была отдана друзьям.