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

int v[10], dj[10],dp[30],ds[30], n,cnt;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
void drj(int n, int pas);

int main(){
    fin >> n;
   drj(n,1);
   fout<<"\n"<<cnt;
}
void drj(int n, int pas){
    if(pas==n+1){
            cnt++;
        if(cnt==1){
        for(int i = 1; i <= n; i++ )
            fout<<dj[i]<<" ";

        }
    }

    else{
        for(int i=1;i<=n;i++){
            if(v[i]==0&&dp[i+pas]==0&&ds[i-pas+n]==0){
                dj[pas]=i;
                v[i]=1,dp[i+pas]=1,ds[i-pas+n]=1;
                drj(n,pas+1);
                v[i]=0,dp[i+pas]=0,ds[i-pas+n]=0;
            }
        }
    }
}