using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace Permutations
{
    /// <summary>
    /// リストの拡張メソッド
    /// </summary>
    public static class MyListExtensions
    {
        /// <summary>
        /// 人間が読みやすいように表示
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list"></param>
        /// <returns></returns>
        public static string ToPrettyString<T>(this List<T> list)
        {
            var str = new StringBuilder();
            str.Append(string.Format("[ n = {0}", list.Count));
            if (list.Count > 0)
            {
                str.Append(" : ");
                for (var i = 0; i < list.Count; ++i)
                {
                    var e = list[i];
                    str.Append(e.ToString());
                    if (i < list.Count - 1)
                        str.Append(", ");
                }
            }
            str.Append(" ]");
            return str.ToString();
        }
    }
 
    class Program
    {
        static void Main(string[] args)
        {
            var list = new List<int>(Enumerable.Range(1, Convert.ToInt32(Console.ReadLine())));
            var results = Permutations(list);
            Console.WriteLine("length = {0}", results.Count);
            foreach (var r in results)
                Console.WriteLine(r.ToPrettyString());
            Console.ReadKey();
        }
 
        static List<List<T>> _Permutations<T>(List<T> list, List<T> result)
        {
            if (list.Count <= 0)
                return new List<List<T>>() { result };
 
            var result1 = new List<List<T>>();
            for (var i = 0; i < list.Count; ++i)
            {
                var n = list[i];
                var result2 = new List<T>(result);
                result2.Add(n);
                var list2 = list.Take(i).Concat(list.Skip(i + 1)).ToList();
                result1.AddRange(_Permutations(list2, result2));
            }
            return result1;
        }
 
        /*
        [1, 2, 3]の順列を列挙する
        最初の要素を取って、残りの要素たちを再起でつなげる
        */
        static List<List<T>> Permutations<T>(List<T> list)
        {
            return new List<List<T>>(_Permutations(list, new List<T>()));
        }
    }
}
 

dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKdXNpbmcgU3lzdGVtLkxpbnE7CnVzaW5nIFN5c3RlbS5UZXh0Owp1c2luZyBTeXN0ZW0uVGhyZWFkaW5nLlRhc2tzOwoKbmFtZXNwYWNlIFBlcm11dGF0aW9ucwp7CiAgICAvLy8gPHN1bW1hcnk+CiAgICAvLy8g44Oq44K544OI44Gu5ouh5by144Oh44K944OD44OJCiAgICAvLy8gPC9zdW1tYXJ5PgogICAgcHVibGljIHN0YXRpYyBjbGFzcyBNeUxpc3RFeHRlbnNpb25zCiAgICB7CiAgICAgICAgLy8vIDxzdW1tYXJ5PgogICAgICAgIC8vLyDkurrplpPjgYzoqq3jgb/jgoTjgZnjgYTjgojjgYbjgavooajnpLoKICAgICAgICAvLy8gPC9zdW1tYXJ5PgogICAgICAgIC8vLyA8dHlwZXBhcmFtIG5hbWU9IlQiPjwvdHlwZXBhcmFtPgogICAgICAgIC8vLyA8cGFyYW0gbmFtZT0ibGlzdCI+PC9wYXJhbT4KICAgICAgICAvLy8gPHJldHVybnM+PC9yZXR1cm5zPgogICAgICAgIHB1YmxpYyBzdGF0aWMgc3RyaW5nIFRvUHJldHR5U3RyaW5nPFQ+KHRoaXMgTGlzdDxUPiBsaXN0KQogICAgICAgIHsKICAgICAgICAgICAgdmFyIHN0ciA9IG5ldyBTdHJpbmdCdWlsZGVyKCk7CiAgICAgICAgICAgIHN0ci5BcHBlbmQoc3RyaW5nLkZvcm1hdCgiWyBuID0gezB9IiwgbGlzdC5Db3VudCkpOwogICAgICAgICAgICBpZiAobGlzdC5Db3VudCA+IDApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHN0ci5BcHBlbmQoIiA6ICIpOwogICAgICAgICAgICAgICAgZm9yICh2YXIgaSA9IDA7IGkgPCBsaXN0LkNvdW50OyArK2kpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgdmFyIGUgPSBsaXN0W2ldOwogICAgICAgICAgICAgICAgICAgIHN0ci5BcHBlbmQoZS5Ub1N0cmluZygpKTsKICAgICAgICAgICAgICAgICAgICBpZiAoaSA8IGxpc3QuQ291bnQgLSAxKQogICAgICAgICAgICAgICAgICAgICAgICBzdHIuQXBwZW5kKCIsICIpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIHN0ci5BcHBlbmQoIiBdIik7CiAgICAgICAgICAgIHJldHVybiBzdHIuVG9TdHJpbmcoKTsKICAgICAgICB9CiAgICB9CgogICAgY2xhc3MgUHJvZ3JhbQogICAgewogICAgICAgIHN0YXRpYyB2b2lkIE1haW4oc3RyaW5nW10gYXJncykKICAgICAgICB7CiAgICAgICAgICAgIHZhciBsaXN0ID0gbmV3IExpc3Q8aW50PihFbnVtZXJhYmxlLlJhbmdlKDEsIENvbnZlcnQuVG9JbnQzMihDb25zb2xlLlJlYWRMaW5lKCkpKSk7CiAgICAgICAgICAgIHZhciByZXN1bHRzID0gUGVybXV0YXRpb25zKGxpc3QpOwogICAgICAgICAgICBDb25zb2xlLldyaXRlTGluZSgibGVuZ3RoID0gezB9IiwgcmVzdWx0cy5Db3VudCk7CiAgICAgICAgICAgIGZvcmVhY2ggKHZhciByIGluIHJlc3VsdHMpCiAgICAgICAgICAgICAgICBDb25zb2xlLldyaXRlTGluZShyLlRvUHJldHR5U3RyaW5nKCkpOwogICAgICAgICAgICBDb25zb2xlLlJlYWRLZXkoKTsKICAgICAgICB9CgogICAgICAgIHN0YXRpYyBMaXN0PExpc3Q8VD4+IF9QZXJtdXRhdGlvbnM8VD4oTGlzdDxUPiBsaXN0LCBMaXN0PFQ+IHJlc3VsdCkKICAgICAgICB7CiAgICAgICAgICAgIGlmIChsaXN0LkNvdW50IDw9IDApCiAgICAgICAgICAgICAgICByZXR1cm4gbmV3IExpc3Q8TGlzdDxUPj4oKSB7IHJlc3VsdCB9OwoKICAgICAgICAgICAgdmFyIHJlc3VsdDEgPSBuZXcgTGlzdDxMaXN0PFQ+PigpOwogICAgICAgICAgICBmb3IgKHZhciBpID0gMDsgaSA8IGxpc3QuQ291bnQ7ICsraSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgdmFyIG4gPSBsaXN0W2ldOwogICAgICAgICAgICAgICAgdmFyIHJlc3VsdDIgPSBuZXcgTGlzdDxUPihyZXN1bHQpOwogICAgICAgICAgICAgICAgcmVzdWx0Mi5BZGQobik7CiAgICAgICAgICAgICAgICB2YXIgbGlzdDIgPSBsaXN0LlRha2UoaSkuQ29uY2F0KGxpc3QuU2tpcChpICsgMSkpLlRvTGlzdCgpOwogICAgICAgICAgICAgICAgcmVzdWx0MS5BZGRSYW5nZShfUGVybXV0YXRpb25zKGxpc3QyLCByZXN1bHQyKSk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmV0dXJuIHJlc3VsdDE7CiAgICAgICAgfQoKICAgICAgICAvKgogICAgICAgIFsxLCAyLCAzXeOBrumghuWIl+OCkuWIl+aMmeOBmeOCiwogICAgICAgIOacgOWIneOBruimgee0oOOCkuWPluOBo+OBpuOAgeaui+OCiuOBruimgee0oOOBn+OBoeOCkuWGjei1t+OBp+OBpOOBquOBkuOCiwogICAgICAgICovCiAgICAgICAgc3RhdGljIExpc3Q8TGlzdDxUPj4gUGVybXV0YXRpb25zPFQ+KExpc3Q8VD4gbGlzdCkKICAgICAgICB7CiAgICAgICAgICAgIHJldHVybiBuZXcgTGlzdDxMaXN0PFQ+PihfUGVybXV0YXRpb25zKGxpc3QsIG5ldyBMaXN0PFQ+KCkpKTsKICAgICAgICB9CiAgICB9Cn0K

NQ==

5