//
//  main.cpp
//  C++ - teste
//
//  Created by Filip Cuciuc on 03/02/2020.
//  Copyright © 2020 Filip Cuciuc. All rights reserved.
//

#include <iostream>
#include <fstream>
//#include <algorithm>
//#include "MED.h"
using namespace std;


//int main() {
//    MED a;
//    cin >> a.n >> a.H;
//    for (int i = 1; i <= a.n; i++) {
//        cin >> a.cub[i].first >> a.cub[i].second;
//    }
//    a.turn_genereaza(1);
//
//    return 0;
//}


 
 
ifstream in("damesah.in");
ofstream out("damesah.out");
int n;
int p[200];
int used[105];
   int S = 0;
   int diagonala_prin[105] = {0};
   int diagonala_sec[105] = {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;
}