#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1000;
int mat[NMAX+1][NMAX+1];
int n, show, cnt;
int ans[NMAX+1];
int ans2[NMAX+1];
int trecut[NMAX+1];
int trecut2[NMAX+1];
int trecut3[2*NMAX+1];

int fun(int nr)
{
    if(nr)return nr;
    return abs(nr*100);
}

void bck(int pos)
{
    if(pos == n+1)
    {
        cnt++;
        if(!show)
        {
            for(int i=1; i<=n; i++)
                fout << ans[i] << ' ';
            show = 1;
        }
    }
    else
    {
        for(int i=1; i<=n; i++)
        {
            if(!trecut[i] && !trecut2[fun(pos-i)] && !trecut3[pos+i])
            {
                //cout << pos << "->" << i << '\n';
                trecut[i] = 1;
                trecut2[fun(pos-i)] = 1;
                trecut3[pos+i] = 1;
                ans[pos] = i;
                bck(pos+1);
                trecut[i] = 0;
                trecut2[fun(pos-i)] = 0;
                trecut3[pos+i] = 0;
            }
        }
    }
}

int main()
{
    fin >> n;
    bck(1);
    fout << '\n' <<  cnt;
    return 0;
}