#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int n, cnt=0;

int sol[15];
bool coloana[15];
bool diag1[30];
bool diag2[30];

bool e_sol(int k){

    return k==n+1;
}

bool valid(int k, int col){
    if(coloana[col])
        return false;
    if(diag1[k - col + n])
        return false;
    if(diag2[k + col])
        return false;
    return true;
}

void afis(){

    for(int i=1; i<=n; i++)
        fout<<sol[i]<<" ";
    fout<<'\n';
}

void backtrack(int lin){

    if(e_sol(lin)==true){
        cnt++;
        if(cnt==1)
            afis();
        return;
    }

    for(int col=1; col<=n; col++)
    {
        if(valid(lin, col)==true){

            sol[lin]=col;
            coloana[col]=true;
            diag1[lin-col+n]=true;
            diag2[lin+col]=true;

            backtrack(lin+1);

            coloana[col]=false;
            diag1[lin-col+n]=false;
            diag2[lin+col]=false;

        }
    }
}


int main()
{
    fin>>n;
    backtrack(1);
    fout<<cnt;

    return 0;
}