#include <fstream>

using namespace std;

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

int n, k, cnt, s[15];
int diagprin[35], diagsec[35], col[15];

int valid(int k, int i){
    if(col[i] == 1)
        return 0;
    if(diagprin[k+i-1] == 1)
        return 0;
    if(diagsec[n-k+i] == 1)
        return 0;
    return 1;
}


void perm(int k){
    if(k == n+1){
        cnt++;
        if(cnt == 1){
            for(int i=1; i<=n; i++)
                fout << s[i] << ' ';
            fout << '\n' << cnt+1;
        }
    }
    else
        for(int i=1; i<=n; i++)
            if(valid(k, i)){
                diagprin[k+i-1] = 1;
                col[i]=1;
                diagsec[n-k+i]=1;
                s[k]=i;
                perm(k + 1);
                diagprin[k+i-1]=0;
                col[i]=0;
                diagsec[n-k+i]=0;
            }
}

int main()
{
    fin >> n;
    perm(1);
    return 0;
}