#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("damesah.in");
ofstream g ("damesah.out");
int n,nr,v[20],sol[20],diag1[101],diag2[101],col[101],k,i;
 
bool valid(int k)
{
    if(col[v[k]]==0 and diag1[k-v[k]+n]==0 and diag2[k+v[k]]==0 and v[k]>0) return true;
    return false;
}
 
int main()
{
    f >> n;
    k=1;
    while(k>0) {
        if(v[k]!=0) {
            col[v[k]]=0;
            diag1[k-v[k]+n]=0;
            diag2[k+v[k]]=0;
        }
        v[k]++;
        while( v[k]<=n and valid(k)==false) v[k]++;
        if(v[k]>n) {
            k--;
        }
        else {
            col[v[k]]=1;
            diag1[k-v[k]+n]=1;
            diag2[k+v[k]]=1;
            if(k==n) {
                if(sol[1]==0) for(i=1; i<=n; i++) sol[i]=v[i];
                nr++;
            }
            else {
                k++;
                v[k]=0;
            }
        }
    }
    for(i=1; i<=n; i++) g << sol[i] << " ";
    g << "\n" << nr;
    return 0;
}