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>()));
        }
    }
}