#include <bits/stdc++.h>

using namespace std;
int n;
long long counter;
bitset<30>col,dr,st;
vector<int>ans,now;
void bkk(int pos)
{
    if(pos==n+1)
    {
        counter++;
        bool k=1;
        if(ans.size()==0)
        {
            for(int i=0;i<n;i++)
                ans.push_back(now[i]);
        }
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(col[i])
            continue;
        if(st[i+pos])
            continue;
        if(dr[n-pos+i])
            continue;
        col[i]=1;
        st[i+pos]=1;
        dr[n-pos+i]=1;
        now.push_back(i);
        bkk(pos+1);
        col[i]=0;
        st[i+pos]=0;
        dr[n-pos+i]=0;
        now.erase(now.begin()+pos-1);
    }
}
int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    bkk(1);
    for(int i=0;i<n;i++)
    printf("%d ",ans[i]);
    printf("\n%d",counter);
    return 0;
}