#include <fstream>
#define VAL 15

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int N, i, sol;
int v[VAL];
int s[VAL];
bool ok[VAL];

bool verificare(int I, int K)
{
    int i, d;
    for (i=1; i<=K-1; i++)
    {
        d=max(I, v[i])-min(I, v[i]);
        if (d==K-i)
          return false;
    }
    return true;
}

void backtr(int K)
{
    int i, j;
    for (i=N; i>=1; i--)
    {
        if (ok[i]==false && verificare(i, K)==true)
        {
            ok[i]=true;
            v[K]=i;
            if (K==N)
            {
                for (j=1; j<=N; j++)
                  s[j]=v[j];
                sol++;
            }
            backtr(K+1);
            ok[i]=false;
        }
    }
}

int main()
{
    fin >> N;
    backtr(1);
    for (i=1; i<=N; i++)
      fout << s[i] << " ";
    fout << '\n';
    fout << sol << '\n';
    fin.close();
    fout.close();
    return 0;
}