I. Игрушки
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Маленькая девочка Маша любит раскладывать свои игрушки в кучки на полу. А еще она очень не любит, когда кто-нибудь трогает ее игрушки. Как-то раз Маша аккуратно разложила все свои n игрушек в несколько кучек, а затем ее старший брат Саша пришел и собрал все кучки в одну. Маша увидела это, страшно расстроилась и принялась плакать. У Саши никак не получается успокоить Машу, а скоро придет мама и ему влетит за то, что сестренка плачет. Поэтому он решает восстановить разложение игрушек по кучкам. Однако он совершенно не помнит, как лежали игрушки. Маша, конечно, помнит это, но она еще не умеет говорить и может помочь Саше лишь тем, что радостно завопит, когда он выложит игрушки именно так, как они и лежали. Значит, Саше придется раскладывать игрушки всеми возможными способами до тех пор, пока Маша не узнает нужное разложение. Взаимное расположение кучек и игрушек в каждой кучке не важно, поэтому два способа разложить игрушки считаются различными, если найдутся две такие игрушки, которые при одном из способов лежат в одной и той же кучке, а при другом нет. Саша ищет наиболее быстрый путь перебора всех способов, потому что скоро придет мама. За одно действие Саша может взять игрушку из любой кучки и переложить ее в любую другую кучку (возможно, при этом появится новая кучка или одна из кучек исчезнет). Саша хочет найти такую последовательность действий, что в процессе все способы разложить игрушки на кучки будут перебраны ровно по одному разу. Помогите Саше. Изначально, как мы помним, все игрушки находятся в одной кучке.

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

В первой строке записано целое число n (1 ≤ n ≤ 10) — число игрушек.

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

В первой строке выведите количество различных способов разложить игрушки на кучки. Далее выведите все способы разложить игрушки на кучки в том порядке, в каком их должен перебирать Саша (т.е. каждый следующий способ должен получаться из предыдущего описанной в условии операцией). Каждый способ надо выводить следующим образом. В каждой кучке игрушки надо упорядочить по возрастанию номера. После этого надо упорядочить кучки по возрастанию номеров первых игрушек в них. Каждый способ выводите в отдельной строке. См. пример для уточнения формата выходных данных. Если решений несколько, выведите любое из них.

Примеры
Входные данные
3
Выходные данные
5
{1,2,3}
{1,2},{3}
{1},{2,3}
{1},{2},{3}
{1,3},{2}