#include <iostream>
#include <fstream>

using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");

int a[100][100], n;

int verif_l(int l)
    {
        for(int j=1; j<=n; j++)
            if(a[l][j]==1)
                return 0;
        return 1;
    }

int verif_c(int c)
    {
        for(int i=1; i<=n; i++)
            if(a[i][c]==1)
                return 0;
        return 1;
    }

int verif_diagp_up(int l, int c)
    {
        if(l<1 || c<1)
            return 1;
        if(a[l][c]==1)
            return 0;
        verif_diagp_up(l-1, c-1);
    }

int verif_diagp_down(int l, int c)
    {
        if(l>n || c>n)
            return 1;
        if(a[l][c]==1)
            return 0;
        verif_diagp_down(l+1, c+1);
    }

int verif_diags_up(int l, int c)
    {
        if(l<1 || c>n)
            return 1;
        if(a[l][c]==1)
            return 0;
        verif_diagp_up(l-1, c+1);
    }
int verif_diags_down(int l, int c)
    {
        if(l>n || c<1)
            return 1;
        if(a[l][c]==1)
            return 0;
        verif_diags_down(l+1, c-1);
    }
struct pct{

    int x, y;

}stiv[1000];
int r=1, ok=0, kont=0;
void bk(int l, int c, int k)
    {
        if(k==n && ok==0)
        {
            for(int ii=1; ii<=n; ii++)
                for(int jj=1; jj<=n; jj++)
                    if(a[ii][jj]==1)
                        {
                            stiv[r].y=jj;
                            r++;
                        }
            ok=1;
            kont++;
            return;
        }
        if(k==n && ok==1)
            kont++;
        if(c>n)
            return;
        for(int i=1; i<=n; i++)
            {
                if(verif_l(i) && verif_c(c) && verif_diagp_down(i, c) && verif_diagp_up(i, c) && verif_diags_down(i, c) && verif_diags_up(i, c))
                {
                    a[i][c]=1;
                    bk(1, c+1, k+1);
                    a[i][c]=0;
                    bk(1, c+1, k-1);

                }
                if(i==n)
                    bk(1, c+1, k);
            }
    }

int main()
    {
        cin>>n;
        bk(1, 1, 0);
        r--;
        for(int i=r; i>=1; i--)
            g<<stiv[i].y<<" ";
        g<<endl;
        g<<kont;
    }