#include <iostream>
#include <fstream>

const int MAXN = 30;
const int dx[] = {-1,-1,-1,0,1,1,1,0};
const int dy[] = {-1,0,1,1,1,0,-1,-1};

using namespace std;

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

int n,cnt,ans[MAXN];
bool linie[MAXN],coloana[MAXN],diag1[MAXN],diag2[MAXN];

bool validare(int x,int y){
    if(linie[x] || coloana[y] || diag1[x - y + n] || diag2[x + y])
        return false;
    return true;
}

void backtracking(int k){
    if(k == n + 1){
        if(cnt == 0){
            for(int i = 1; i <= n; ++i){
                out<<ans[i]<<" ";
            }
            out<<"\n";

        }
        cnt++;
    }


    for(int j = 1; j <= n; ++j){
        if(validare(k,j)){
            ans[k] = j;
            linie[k] = true;
            coloana[j] = true;
            diag1[k - j + n] = true;
            diag2[j + k] = true;
            backtracking(k + 1);
            diag1[k - j + n] = false;
            diag2[j + k] = false;
            linie[k] = false;
            coloana[j] = false;
        }
    }

}

int main()
{
    in.tie(NULL);
    out.tie(NULL);
    ios::sync_with_stdio(false);
    in>>n;
    backtracking(1);
    out<<cnt;
    return 0;
}