#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int x[100],v[100];
int n,i,nrsol=0,nr=0;;
void sol(int n){
    nrsol++;
    if(nrsol==1){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(x[i]==j)
                    v[++nr]=j;
            }
        }
    }
}
int modul(int a){
    if (a>=0)
        return a;
    else
        return -a;
}
int cont(int k){
    for(int i=1;i<k;i++)
        if(x[k]==x[i]  || (modul(k-i)==modul(x[k]-x[i])))
            return 0;
    return 1;
}
void back(int k){
    if(k==n+1){
        sol(n);
    }else{
        for(int i=1;i<=n;i++){
            x[k]=i;
            if(cont(k)){
                back(k+1);
            }
        }
    }
}
int main(){
    fin>>n;
    back(1);
    for(i=1;i<=nr;i++){
        fout<<v[i]<<" ";
    }
    fout<<"\n";
    fout<<nrsol<<"\n";
}