#include<iostream>
#include<fstream>
#include<algorithm>
#include<bitset>
#include<algorithm>
using namespace std;
bool b;
int cont;

ofstream so("damesah.out");
void afis(int n,int v[])
{
    int i;
    for(i=0;i<n;++i)
        so<<v[i]+1<<' ';
    b=true;
}
void dame(int n)
{
    int p;
    int v[n],i;
    for(i=0;i<n;++i)
        v[i]=-1;
    p=0;
    int j;
    while(p>=0)
    {
        for(i=v[p]+1;i<n;++i)
        {
            for(j=0;j<p;++j)
            {
                if(i==v[j])
                    break;
                if(v[j]+p-j==i)
                    break;
                if(v[j]-p+j==i)
                    break;
            }
            if(j==p)
            {
                v[p]=i;
                ++p;
                break;
            }
        }
        if(i==n)
        {
            v[p]=-1;
            --p;
        }
        if(p==n)
        {
            if(b==false)
                afis(n,v);
            ++cont;
            --p;
        }
    }
}
int main()
{
    ifstream si;
    si.open("damesah.in");

    int n;
    si>>n;
    dame(n);
    so<<'\n'<<cont<<'\n';
}