#include <cstdlib>
#include <fstream>
#include <iostream>

using namespace std;

int n,st[1003],cnt;
bool viz[1003];

inline void Citire()
{
    ifstream fin("damesah.in");
    fin>>n;
    fin.close();
}

ofstream fout("damesah.out");

inline void Afisare()
{
    int i;
    cnt++;
    if(cnt==1)
    {
        for(i=1;i<=n;++i)
            fout<<st[i]<<" ";
        fout<<"\n";
    }
}

inline bool Valid(int x,int k)
{
    int i;
    if(viz[x]==1)
        return false;
    for(i=1;i<k;++i)
        if(abs(k-i)==abs(x-st[i]))
            return false;
    return true;
}

inline void Back(int k)
{
    int i;
    if(k==n+1)
        Afisare();
    else
        for(i=1;i<=n;++i)
            if(Valid(i,k))
            {
                st[k]=i;
                viz[i]=true;
                Back(k+1);
                viz[i]=false;
            }

}

int main()
{
    Citire();
    Back(1);
    fout<<cnt<<"\n";
    fout.close();
    return 0;
}