#include <iostream>
using namespace std;
struct solutii {
int x, y;
};
int n;
bool solutie(int k) {
if (k==n) return true;
else return false;
}
void afisare_rezultat(solutii *v) {
for (int i = 0; i < n; i++)
cout << v[i].y+1 << " ";
}
void punere_diag(int x, int y, int *diag_1, int *diag_2) {
if (y - x >= 0) diag_1[y - x] = 1;
else diag_1[n + x - y - 1] = 1;
diag_2[x + y] = 1;
}
void scoatere_diag(int x, int y, int *diag_1, int *diag_2) {
if (y - x >= 0) diag_1[y - x] = 0;
else diag_1[n + x - y - 1] = 0;
diag_2[x + y] = 0;
}
void adaugare_solutii(int x, int y, solutii *v) {
v[x].x = x;
v[x].y = y;
}
bool continuare(int x, int y, int *diag_1, int *diag_2, int *coloane) {
if (coloane[y] == 1) return false;
if (y - x >= 0 && (diag_1[y - x] == 1 || diag_2[x + y] == 1)) return false;
if (y - x <0 && (diag_1[n + x - y - 1] == 1 || diag_2[x + y] == 1)) return false;
return true;
}
void back_track(int k, int *diag_1, int *diag_2, int *coloane,solutii *v,int &first_time,int &counter) {
if (solutie(k)) {
if (first_time) {
afisare_rezultat(v);
first_time = false;
cout << endl;
}
counter++;
}
for (int i = 0; i<n; i++)
if (continuare(k, i, diag_1, diag_2, coloane)) {
coloane[i] = 1;
punere_diag(k, i, diag_1, diag_2);
adaugare_solutii(k, i, v);
back_track(k + 1, diag_1, diag_2, coloane,v,first_time,counter);
coloane[i] = 0;
scoatere_diag(k, i, diag_1, diag_2);
}
}
int main()
{
int diag_1[10], diag_2[10], coloane[10],first_time=true,counter=0;
solutii v[10];
cin >> n;
back_track(0, diag_1, diag_2, coloane, v,first_time,counter);
cout << counter<<endl;
return 0;
}