#include <iostream>
#include <fstream>
#define m 20

using namespace std;

ifstream in("damedesah.in");
ofstream out("damedesah.out");

int c[30],d1[30],d2[30],v[30],nr,n;

bool ok(int a)
{
    return ( c[ v[a] ] || d1[ m + a - v[a] ] || d2[ a + v[a] ]);
   // for(int i=1;i<a;i++)
}
void backt(int k)
{
    int i;
    for(i=1 ; i<=n ; ++i)
    {
        v[k]=i;
        if( ok(k) )
        {
            if(k == n)
            {
                if(!nr)
                    for(int j=1 ; j<=n ; ++j)
                        out<<v[j]<<" ";
                ++nr;
            }
        }
        else
        {
            c[i]=1;
            d1[/*m + */k - i] = 1;
            d2[k + i] = 1;
            backt(k + 1);
            c[i]=0;
            d1[/*m + */k - i] = 0;
            d2[k + i] = 0;
        }
    }
}
int main()
{
    in>>n;
    backt(1);
    out<<'\n'<<nr;
    return 0;
}