#include <fstream>

using namespace std;

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

int e_sol(int st[], int k, int n)
{
    if (k==n)
        return 1;
    return 0;
}

int suc(int st[], int k, int n)
{
    if (st[k]==n+1)
        return 0;
    return 1;
}

int e_valid(int st[], int k,int n, bool col[], bool diagp[], bool diags[])
{
    if (col[st[k]]==0 && diagp[n+1-st[k]+k-1]==0 && diags[st[k]+k-1]==0)
        return 1;
    return 0;
}

int main()
{
    int n;
    fin>>n;
    int k=1, contor=0;
    int st[n+1];
    st[1]=0;
    bool col[n+1], diagp[2*n], diags[2*n];
//    col[1]=0;
//    diags[1]=0;
//    diagp[n]=0;
    for (int i=1; i<2*n; i++)
    {
        if (i<=n)
            col[i]=0;
        diagp[i]=0;
        diags[i]=0;
    }
    while(k)
    {
        do
        {
            st[k]++;
        }while(suc(st, k, n) && !e_valid(st, k, n, col, diagp, diags));
        if (suc(st, k, n))
        {
            diags[st[k]+k-1]=1;
            diagp[n+1-st[k]+k-1]=1;
            col[st[k]]=1;
            if (e_sol(st, k, n))
            {
                if (!contor)
                    for (int i=1; i<=n; i++) fout<<st[i]<<" ";
                contor++;
                diags[st[k]+k-1]=0;
                diagp[n+1-st[k]+k-1]=0;
                col[st[k]]=0;
            }
            else
            {
                k++;
                st[k]=0;
//                diags[st[k]+k-1]=0;
//                diagp[n+1-st[k]+k-1]=0;
//                col[k]=0;
            }
        }
        else
        {
            st[k]=0;
            k--;
            if (k>0)
            {
            diags[st[k]+k-1]=0;
            diagp[n+1-st[k]+k-1]=0;
            col[st[k]]=0;
            }
        }
    }
    fout<<"\n"<<contor;


    return 0;
}