#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

ifstream fin ("damesah.in") ;
ofstream fout ("damesah.out") ;

int x[20] , N ;
bool Valid ( int k )
{
    for ( int i = 1 ; i < k ; ++ i )
            {
                if ( x [i] == x [k] )
                    return false ;

                if ( k - i == abs ( x[k] - x[i]) )
                    return false ;
            }

    return 1 ;
}

void Afisare ()
{
   for ( int i = 1 ; i <= N ; ++ i )
     for ( int j = 1 ; j <= N ; ++ j )
           if ( x[i] == j )
                  fout << j << " " ;

}

int nr_sol ;
void Back ( int k )
{
    for ( int i = 1 ; i <= N ; ++ i )
    {
        x [k] = i ;
        if ( Valid (k) )
             {
                if ( k == N )
                {
                    ++ nr_sol ;
                    if ( nr_sol == 1 )
                       Afisare () ;
                }

                else
                    Back ( k + 1 ) ;
             }
    }
}

int main()
{
    fin >> N ;
    Back (1) ;
    fout << "\n" << nr_sol ;
    return 0;
}