#include<fstream>
#include<vector>
#include<queue>
#include<cmath>
#include<iostream>

using namespace std;

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

int sol[20],n,nr;

int verif(int k)
{
    int i;
    for(i=1;i<k;i++)
        if(sol[i]==sol[k])
            return 0;
    for(i=1;i<k;i++)
        if(abs(sol[i]-sol[k])==abs(i-k))
            return 0;
    return 1;
}

void backt(int k)
{
    int i;
    if(k==n+1){nr++;
        if(nr==1)
            for(i=1;i<=n;i++)
                g<<sol[i]<<" ";
    }
    else{
        for(sol[k]=1;sol[k]<=n;sol[k]++)
            if(verif(k))
                backt(k+1);
    }
}

int main()
{
    f>>n;
    backt(1);
    g<<"\n"<<nr<"\n";
    return 0;
}