#include <bits/stdc++.h>

using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n,st[101],nivel,nrsol,main_diag[101],sec_diag[101],lin[101],col[101];
int main()
{
    fin>>n;
    nivel=1;
    while(nivel)
    {
        if(st[nivel]<n)
        {
            if(st[nivel]>0)
            {
                int l=nivel;
                int c=st[nivel];
                main_diag[l-c+30]--;
                sec_diag[l+c]--;
                lin[l]--;
                col[c]--;
            }
            st[nivel]++;
            bool ok=1;
            int l=nivel;
            int c=st[nivel];
            main_diag[l-c+30]++;
            sec_diag[l+c]++;
            lin[l]++;
            col[c]++;
            if(main_diag[l-c+30]>1||sec_diag[l+c]>1||lin[l]>1||col[c]>1)
                ok=0;
            if(ok)
            {
                if(nivel==n)
                {
                    nrsol++;
                    if(nrsol==1)
                        for(int i=1;i<=n;i++)
                            fout<<st[i]<<" ";
                }
                if(nivel<n)
                {
                    nivel++;
                    st[nivel]=0;
                }
            }
        }
        else
        {
            int l=nivel;
            int c=st[nivel];
            main_diag[l-c+30]--;
            sec_diag[l+c]--;
            lin[l]--;
            col[c]--;
            st[nivel]=0;
            nivel--;
        }
    }
    fout<<'\n'<<nrsol;
    return 0;
}