#include <iostream>
#include <fstream>
using namespace std;


ifstream in("damesah.in");
ofstream out("damesah.out");
int n;
int p[10];
int used[105];
   int S = 0;
   int diagonala_prin[10] = {0};
   int diagonala_sec[10] = {0};
   
   void afiseaza_Solutii(){
       out << S;
   }
   
   void damesah(int poz) {
       if (poz == n + 1) {
           S++;
           if(S == 1) {
            for (int i = 1; i <= n; i++) {
               out << p[i] << " ";
            }
            out << '\n';
           }
             return;
        }
       
      for (int i = 1; i <= n; i++) {
           if (!used[i] && !diagonala_prin[poz - i + n] && !diagonala_sec[i + poz]) {
               p[poz] = i;
               used[i] = 1;
               diagonala_prin[poz - i + n] = 1;
               diagonala_sec[i + poz] = 1;
               
               damesah(poz+1);
               
              used[i] = 0;
              diagonala_prin[poz - i + n] = 0;
              diagonala_sec[i + poz] = 0;
           }
       }
       
       
   }

int main() {
    in >> n;
    damesah(1);
    afiseaza_Solutii();
    return 0;
}