#include <iostream>
#include <fstream>

using namespace std;

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

int v[20], f[20];
int n, placed, ok, sol;

int mod(int x){
    if(x < 0) return -x; return x;
}

void bt(int k){
    if(k > n){
        if(placed == 0){
            for(int i=1; i<=n; i++)
                fout<<v[i]<<" ";
            placed=1;
        }
        sol++;
        return;
    }

    for(int i=1; i<=n; i++)
        if(f[i] == 0){
            ok=1;
            for(int j=1; j<k; j++)
                if(mod(v[j] - i) == k-j){
                    ok=0;
                    break;
                }

            if(ok == 1){
                f[i]=1;
                v[k]=i;
                bt(k+1);
                f[i]=0;
            }
        }
}

int main (){
    fin>>n;
    bt(1);
    fout<<"\n"<<sol;
    return 0;
}