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