#include <bits/stdc++.h>

using namespace std;
ifstream fin ("damesah.in");
ofstream fout ("damesah.out");
int n,k,x[15],v[15],a[15][15],nr;
int verif(int k)
{
    for(int i=1;i<k;i++)
        if(k-i==x[k]-x[i] or k+x[k]==i+x[i])
            return 0;
    return 1;
}
void Back(int k)
{
    for(int i=1;i<=n;i++)
    {
        if(v[i]==0)
        {
            v[i]=1;
            x[k]=i;
            if(verif(k))
            {
                if(k==n)
                {

                    if(nr==0)
                    {
                        for(int j=1;j<=n;j++)
                        {
                            fout<<x[j]<<" ";
                        }
                    }
                    nr++;
                }
                else
                    Back(k+1);
            }
            v[i]=0;
        }
    }
}
int main()
{
    fin>>n;
    Back(1);
    fout<<"\n"<<nr;
    return 0;
}