#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 13;

int n, queen[MAXN];
bool column[MAXN * 2], maindiag[MAXN * 2], secdiag[MAXN * 2];
int cnt = 0;

void backtrack(int l = 0) {
    if (l == n) {
        cnt++;
        
        if (cnt == 1) {
            for (int i = 0; i < n; i++) {
                cout << queen[i] + 1 << ' ';
            }
            cout << '\n';
        }
    } else {
        for (int c = 0; c < n; c++) {
            int maindiagIdx = l - c + n - 1;
            int secdiagIdx = l + c;
            
            if (!column[c] && !maindiag[maindiagIdx] && !secdiag[secdiagIdx]) {
                queen[l] = c;
                
                column[c] = maindiag[maindiagIdx] = secdiag[secdiagIdx] = true;
                backtrack(l + 1);
                column[c] = maindiag[maindiagIdx] = secdiag[secdiagIdx] = false;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    ifstream cin("damesah.in");
    ofstream cout("damesah.out");
    
    cin >> n;
    
    backtrack();
    cout << cnt;
    
    return 0;
}