#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;

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

const int MAX_N = 15;
int n, solcnt, sol[MAX_N], placed[MAX_N], freq[MAX_N];

inline bool place(int val, int index){
    for(int i=1; i < index; i++)
        if(abs(val - placed[i]) == abs(index - i))
            return false;
    return true;
}

void bt(int step){
    if(step > n){
        if(solcnt == 0){
            for(int i=1; i<=n; i++)
                sol[i] = placed[i];
        }
        solcnt++;
        return;
    }

    for(int i=1; i<=n; i++)
        if(freq[i] == 0 && place(i, step) == true){
            freq[i] = 1;
            placed[step] = i;
            bt(step+1);
            freq[i] = 0;
        }
}


int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>n;

    bt(1);

    for(int i=1; i<=n; i++)
        fout<<sol[i]<<" ";
    fout<<"\n"<<solcnt;
    return 0;
}