#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n,st[13],a[13],ok=0,nr=0;
int verif(int k)
{
    int i;
    for (i=1;i<=k-1;i++)
    {
        if (st[i]==st[k]||abs(st[i]-st[k])==abs(i-k)) return 0;
    }
    return 1;
}
void afis(int k)
{
    int i,j;
    if (ok==0)
    for (i=1;i<=k;i++)
    {
        for (j=1;j<=k;j++)
        {
            if (st[i]==j) fout <<j<<" ";
        }
    }
    ok=1;
    nr++;
}
int main()
{
    int k;
    fin >>n;
    k=1;
    st[k]=0;
    while (k>0)
    {
        while (st[k]<n)
        {
            st[k]=st[k]+1;
            if (verif(k)==1)
            {
                if (k==n) afis(k);
                else
                {
                    k++;
                    st[k]=0;
                }
            }

        }
        k--;
    }
    fout <<'\n'<<nr;
    return 0;
}