#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f ( "damesah.in" );
ofstream g ( "damesah.out" );
int  n, x[100], nrsol;
void afis()
{
    nrsol++;

    for ( int i = 1; i <= n; i++ )
        g << x[i] << ' ';

    g << '\n';
}
bool valid ( int k )
{
    for ( int i = 1; i < k; i++ )
        if ( x[i] == x[k] || abs ( x[i] - x[k] ) == k - i )
            return 0;

    return 1;
}
void backt()
{
    int k = 1;
    x[1] = 0;

    while ( k > 0 )
        if ( x[k] < n )
        {
            x[k]++;

            if ( valid ( k ) )
            {
                if ( k == n )
                {

                        afis();
                        break;

                }
                else
                    x[++k] = 0;
            }
        }
        else
            k--;
            while ( k > 0 )
        if ( x[k] < n )
        {
            x[k]++;

            if ( valid ( k ) )
            {
                if ( k == n )
                {
                 nrsol++;
                }
                else
                    x[++k] = 0;
            }
        }
        else
            k--;
}
int main()
{
    f >> n;
    backt();
    g << nrsol ;
    return 0;
}