#include <bits/stdc++.h>

using namespace std;
ifstream in ("damesah.in");
ofstream out ("damesah.out");
const int NMAX=15;
int n;
int v[NMAX];
bool gasit=false;
int cnt;
void afis()
{
    for(int i=1; i<=n; i++)
        out<<v[i]<<" ";
    out<<'\n';
    gasit=true;
}
bool ok(int poz)
{
    for(int i=1; i<poz; i++)
    {
        if(v[poz]==v[i])
            return false;
        else if(abs(v[i]-v[poz])==abs(i-poz))
            return false;
    }
    return true;
}
void bkt(int poz)
{
    for(int i=1; i<=n; i++)
    {
        v[poz]=i;
        if(ok(poz))
        {
            if(poz==n)
            {
                if(!gasit)
                    afis();
                cnt++;
            }
            else
                bkt(poz+1);
        }
    }
}
int main()
{
    in>>n;
    bkt(1);
    out<<cnt;
    return 0;
}