#include <fstream>
#define lld long long int
using namespace std;

int N,K,sol[13]; lld res; bool col[20], d1[30],d2[30];

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

void solve(int lin){
    if (lin>N){
        res++;
        if (res==1)
            for (int i=1; i<=K; i++)
                out << sol[i] << " ";

        return;
    }

    for (int i=1; i<=N; i++)
        if (!col[i] && !d1[N+lin-i] && !d2[lin+i-1]){
            sol[++K]=i;
            col[i]=1;
            d1[N+lin-i]=1;
            d2[lin+i-1]=1;
            solve(lin+1);
            K--;
            col[i]=0;
            d1[N+lin-i]=0;
            d2[lin+i-1]=0;
        }
}

int main(){
    in >> N;

    solve(1);
    out << "\n" << res << "\n";
    return 0;
}