#include <cstdio>
#include <cmath>
using namespace std;
bool ok=false;
int sol[14],n,co;
FILE *fin,*fout;
inline bool valid(int k)
{
    for(int i=1;i<k;i++)
        if(sol[i]==sol[k] || abs(sol[i]-sol[k])==abs(i-k))
            return false;
    return true;
}
inline void write()
{
    for(int i=1;i<=n;i++)
        fprintf(fout,"%d ",sol[i]);
}
void back(int k)
{
    if(k==n+1)
    {
        if(!ok)
        {
            write();
            ok=true;
        }
        co++;
    }
    else
        for(int i=1;i<=n;i++)
        {
            sol[k]=i;
            if(valid(k))
                back(k+1);
        }
}
int main()
{
    fin=fopen("damesah.in","r");
    fout=fopen("damesah.out","w");
    fscanf(fin,"%d",&n);
    back(1);
    fprintf(fout,"\n%d",co);
    fclose(fin);
    fclose(fout);
    return 0;
}