#include <fstream>
#include <cmath>

using namespace std;

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

unsigned int sol;
int numOfDameSah;
bool outed;

bool usedCol[15];
int pos[15];
bool a[15][15];
bool usedDiagLR[30];
bool usedDiagRL[30];

void backtrack(int stage) {
    if (stage <= numOfDameSah) {
        for (int i = 1; i <= numOfDameSah; i++)
            if (!usedDiagLR[stage - i + numOfDameSah] && !usedDiagRL[stage + i - 1] && !usedCol[i]) {
                pos[stage] = i;
                usedCol[i] = 1;
                usedDiagLR[stage - i + numOfDameSah] = 1;
                usedDiagRL[stage + i - 1] = 1;
                if (stage == numOfDameSah && !outed) {
                    for (int i = 1; i <= numOfDameSah; i++)
                        cout << pos[i] << " ";
                    outed = 1, sol++;
                } else if (stage == numOfDameSah)
                    sol ++;
                else backtrack(stage + 1);
                pos[stage] = 0;
                usedCol[i] = 0;
                usedDiagLR[stage - i + numOfDameSah] = 0;
                usedDiagRL[stage + i - 1] = 0;
            }
    }
}

int main() {
    cin >> numOfDameSah;
    backtrack(1);
    cout << "\n" << sol;
}