#include <iostream>
#include<fstream>
using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
bool mat[13][13];
bool lines[13];
int n;
void read()
{
    in>>n;
}
bool is_inside(int x,int y)
{
    return x>=0 && x<n && y>=0 &&y<n;
}
bool is_ok(int line,int column)
{
    int x1=column,y1=line;
    while(is_inside(x1,y1))
    {
        x1--;
        y1--;
        if(is_inside(x1,y1)&&mat[y1][x1])
            return false;
    }
    x1=column,y1=line;
    while(is_inside(x1,y1))
    {
        x1--;
        y1++;
        if(is_inside(x1,y1)&&mat[y1][x1])
            return false;
    }
    x1=column,y1=line;
    if(lines[line])
        return false;
    return true;

}
int dame[14];
int i=0;
bool already_found=false;
void backtrack(int column)
{
    if(column==n)
    {
        i++;
        if(!already_found)
        {
            for(int i=0;i<column;i++)
                out<<dame[i]+1<<" ";
            already_found=true;

        }
        return;
    }
    bool found=false;
    for(int i=0; i<n; i++)
    {
        if(is_ok(i,column))
        {
            found=true;
            mat[i][column]=1;
            lines[i]=1;
            dame[column]=i;
            backtrack(column+1);
            mat[i][column]=0;
            lines[i]=0;
        }
    }
    if(!found)
        return;
}
int main()
{
    read();
    backtrack(0);
    out<<endl<<i;
    return 0;
}