#include <fstream>
#include <cmath>
#include <cstring>

using namespace std ;

const int NMAX = 101 ;
const int INF = 0x3f3f3f3f ;

ifstream cin("damesah.in") ;
ofstream cout("damesah.out") ;

int N ;
int C[NMAX], col[NMAX], dsec[NMAX], dprin[NMAX] ;
int NrSol ;

void Rezolvare(int) ;
void Afisare() ;

void Rezolvare(int K)
{
    if(K == N + 1)
        Afisare() ;
    else
    {
        for(int i = 1 ; i <= N ; ++ i)
            if(col[i] == 0 && dprin[i - K + N] == 0 && dsec[i + K - 1] == 0)
            {
                C[K] = i ;
                col[i] = 1 ;
                dprin[i - K + N] = 1 ;
                dsec[i + K - 1] = 1 ;
                Rezolvare(K + 1) ;
                col[i] = 0 ;
                dprin[i - K + N] = 0 ;
                dsec[i + K - 1] = 0 ;
            }

    }


}


inline void Afisare()
{
    ++ NrSol ;
    if(NrSol == 1)
    {
        for(int i = 1 ; i <= N ; ++ i)
            cout << C[i] << ' ' ;
    }
}

int main()
{

    cin >> N ;
    Rezolvare(1) ;
    memset(C, INF, sizeof(C)) ;

    cout <<'\n'<< NrSol << '\n' ;

    cin.close() ;
    cout.close() ;
    return 0;
}