#include<fstream>
using namespace std;
int principala[15][15],secundara[15][15],firstsol[15],n,sol,linie[40],coloana[40],diagonalap[50],diagonalas[50],x[15];

void citire() {

    ifstream in("damesah.in");
    in>>n;
    in.close();

}

void precalcularediagonalaprincipala() {

    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        principala[i][j]=i+j-1;

}

void precalcularediagonalasecundara() {
    int i,j;
    for(i=1;i<=n;i++)
        secundara[1][i]=n-i+1;
    for(i=2;i<=n;i++)
        for(j=1;j<=n;j++)
            secundara[i][j]=secundara[i-1][j]+1;


}

void backtracking (int k) {
    int i,j;
    for(i=1;i<=n;i++) {
        if(linie[i]==1 || coloana[k]==1 || diagonalap[principala[i][k]]==1 || diagonalas[secundara[i][k]]==1)
            continue;

        x[k]=i;
        linie[i]=1;
        coloana[k]=1;
        diagonalap[principala[i][k]]=1;
        diagonalas[secundara[i][k]]=1;
            if(k==n){
                sol++;
                if(sol==1)
                    for(j=1;j<=n;j++)
                        firstsol[j]=x[j];
            }
        if(k<n)
            backtracking(k+1);

        linie[i]=0;
        coloana[k]=0;
        diagonalap[principala[i][k]]=0;
        diagonalas[secundara[i][k]]=0;
    }
}

void solve() {

    precalcularediagonalaprincipala();
    precalcularediagonalasecundara();
    backtracking(1);

}
void afisare() {

    ofstream out("damesah.out");
    int i;
    for(i=1;i<=n;i++)
            out<<firstsol[i]<<" ";
    out<<'\n';
    out<<sol<<'\n';

    out.close();

}

int main () {

    citire();
    solve();
    afisare();
    return 0;

}