#include<fstream>
using namespace std;
ifstream cin("damesah.in");
ofstream cout("damesah.out");

int n,cnt;
int v[35],lex[35];
int dp[35],ds[35],c[35];

void b(int k){

    if(k==n+1){

        if(!lex[1])
            for(int i=1;i<=n;i++)
                lex[i]=v[i];

        ++cnt;

        return;

    }

    for(int i=1;i<=n;i++)
        if(!c[i] && !ds[k+i] && !dp[k-i+n]){

            v[k]=i;

            c[i]=ds[k+i]=dp[k-i+n]=1;

            b(k+1);

            c[i]=ds[k+i]=dp[k-i+n]=0;

        }

}

int main(){

    cin>>n;

    b(1);

    for(int i=1;i<=n;i++)
        cout<<lex[i]<<' ';
    cout<<'\n'<<cnt;

}