#include <bits/stdc++.h>

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


int n,f[20],poz[20],nrsol;

bool diagonale(int q)
{
    for(int i=1;i<q;i++)
        if(abs(q-i)==abs(poz[q]-poz[i]))
            return 0;
    return 1;
}
void backtracking(int x)
{
    if(x==n+1)
    {
        nrsol++;
        if(nrsol==1)
            for(int i=1;i<=n;i++)
            fout<<poz[i]<<' ';
    }
    else
        for(int i=1;i<=n;i++)
            if(f[i]==0)
            {
                f[i]=1;
                poz[x]=i;
                if(diagonale(x)==1)
                    backtracking(x+1);
                f[i]=0;
            }
}
int main()
{
    fin>>n;
    backtracking(1);
    fout<<'\n'<<nrsol;
    return 0;
}