#include <fstream>

using namespace std;

//ifstream cin("input");ofstream cout("output");
ifstream cin("damesah.in");ofstream cout("damesah.out");

int permutare[15];
bool folositColoana[15];
bool d1[35];
bool d2[35];

int n , contRaspunsuri=0;

void backt(int linie){
    if (linie == n+1){
        contRaspunsuri++;
        if (contRaspunsuri==1){
            for (int i=1; i<=n; i++){
                cout<<permutare[i]<<" ";
            }
            cout<<'\n';
        }
        return;
    }
    for (int coloana=1; coloana<=n; coloana++){
        if (!folositColoana[coloana] && !d1[linie-coloana+n] && !d2[coloana+linie]){
            folositColoana[coloana] = true;
            d1[linie-coloana+n]=true;
            d2[coloana+linie]=true;
            permutare[linie] = coloana;

            backt(linie+1);

            folositColoana[coloana] = false;
            d1[linie-coloana+n]=false;
            d2[coloana+linie]=false;
        }
    }
}

int main() {
    cin>>n;
    backt(1);
    cout<<contRaspunsuri;
    return 0;
}