#include <bits/stdc++.h>
#define NMAX 100
using namespace std;
//ifstream fin("dame.in");
//ofstream fout("dame.out");
ifstream fin("damesah.in");
ofstream fout("damesah.out");

int N,Nr;
int sol[NMAX],Sol[NMAX];
bool been[NMAX];

bool diags[2*NMAX],diagdr[2*NMAX];

int valid(int x)
{
    int i=x,j=sol[x];
    int i1=x,j1=sol[x];
    //diagstg
    while(i>1&&j>1) {
            i--;j--;
            if(sol[i]==j) return 0;

    }
    //diagdr
    i=i1,j=j1;
    while(i>1&&j<N)
    {
        i--;
        j++;
        if(sol[i]==j) return 0;
    }
    return 1;
}
void bkt(int k)
{
    if(k==N+1)
    {
        if(Nr==0){
            for(int i=1;i<=N;++i) Sol[i]=sol[i];
        }
        Nr++;
    }
    else{
        for(int i=1;i<=N;++i)
            if(!been[i]&&(!diags[k-i+N])&&(!diagdr[k+i]))
            {

                diags[k-i+N]=1;
                diagdr[k+i]=1;
                been[i]=1;
                sol[k]=i;
                bkt(k+1);
                been[i]=0;

                diags[k-i+N]=0;
                diagdr[k+i]=0;
            }
    }
}
int main()
{
    fin>>N;
    bkt(1);
    for(int i=1;i<=N;++i) fout<<Sol[i]<<" ";
    fout<<endl<<Nr<<endl;
    return 0;
}