#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;
    if (K==N+1)
      return;
    for (i=1; i<=N; i++)
    {
        if (ok[i]==false && verificare(i, K)==true)
        {
            ok[i]=true;
            v[K]=i;
            if (K==N)
            {
                sol++;
                if (sol==1)
                  for (j=1; j<=N; j++)
                    s[j]=v[j];
            }
            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;
}