#include <bits/stdc++.h>

using namespace std;

ifstream fin ("damesah.in");
ofstream fout ("damesah.out");

const int kN = 1e2 + 5;

int ans, n;
int q[kN];
int l[kN], c[kN], ds[kN * 2], dp[kN * 2];

void bkt (int k){
   if (k == n + 1){
      ++ans;
      if (ans == 1){
         for (int i = 1; i <= n; i++){
            fout << q[i] << " ";
         }
      }
   }
   else{
      for (int i = 1; i <= n; i++){
         if (!c[i] && !ds[i + k] && !dp[n - (i - k)]){
            q[k] = i;
            c[i] = true, ds[i + k] = true, dp[n - (i - k)] = true;
            bkt(k + 1);
            c[i] = false, ds[i + k] = false, dp[n - (i - k)] = false;
         }
      }
   }
}

int main(){
   ios_base::sync_with_stdio(false);

   fin >> n;
   bkt(1);
   fout << '\n' << ans;
}