Маша увлекается математикой и программированием, ее уже давно не удивить такими словами, как «Дерево отрезков», «Двойное тестирование», «Пересечение полуплоскостей», или, например, словом «Граф».

Напомним, что графом называется множество пронумерованных вершин, некоторые из которых соединены ребрами. Будем считать, что никакая вершина не должна быть соединена сама с собой, а также что любые две вершины должны быть соединены друг с другом не более, чем одним ребром.

Назовем степенью вершины графа количество ребер, которые соединяют данную вершину с какими-то другими вершинами.

И вот как-то раз Маше стало скучно решать задачи с двойным тестированием, пересекать полуплоскости, строить деревья отрезков и заниматься такими банальными вещами — ведь это так скучно! Вместо этого она придумала себе следующую задачу.

Обозначим за $$$C_k(n)$$$ количество всевозможных графов, состоящих из $$$n$$$ вершин, в которых нет ни одной вершины со степенью $$$k$$$. Маше стало интересно, каких графов больше: графов без вершин со степенью $$$0$$$, или же графов без вершин со степенью $$$n - 1$$$? Иными словами, Маша захотела вычислить разность $$$C_0(n) - C_{n - 1}(n)$$$ для некоторого выбранного $$$n$$$. Попробуйте сделать это и вы!