#include <iostream>
#include <fstream>

using namespace std;

int n, cnt;
int pos[15];
bool colblock[15], diag1block[30], diag2block[30];

ofstream fout("damesah.out");

void backtrack(int lin){
    if(lin == n + 1){
        cnt++;
        if(cnt == 1){
            for(int i = 1; i <= n; ++i)
                fout << pos[i] << " ";
        }
        return;
    }
    for(int col = 1; col <= n; ++col){
        if(!colblock[col] && !diag1block[lin - col + 15] && !diag2block[lin + col]){
            pos[lin] = col;
            colblock[col] = 1;
            diag1block[lin - col + 15] = 1;
            diag2block[lin + col] = 1;
            backtrack(lin + 1);
            colblock[col] = 0;
            diag1block[lin - col + 15] = 0;
            diag2block[lin + col] = 0;
        }
    }
    return;
}

int main()
{
    ifstream fin("damesah.in");
    fin >> n;
    backtrack(1);
    fout << "\n" << cnt;
    return 0;
}