#include <fstream>

using namespace std;

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

#define NMAX 14

int dame[NMAX];
int N;
int nSol;

void backtraking(int);
bool solution(int,int);
void write();


int main()
{

    cin>>N;

    backtraking(1);

    cout<<nSol;

    return 0;
}

void backtraking(int k)
{
    for( int i = 1 ; i <= N ; i++)
        if( solution(k,i) )
        {
            dame[k] = i;

            if( k == N)
                write();

            backtraking(k+1);
        }
}

bool solution(int k,int i)
{
    for( int j = 1 ; j < k ; j++ )
    {
        if( dame[j] == i )
            return false;

        unsigned int ratioC = ( j > k)? j-k : k-j ;
        unsigned int ratioL = ( dame[j] > i )? dame[j] - i : i - dame[j] ;

        if( ratioC == ratioL )
            return false;

    }

    return true;
}

void write()
{
    ++nSol;

    if( nSol == 1 )
    {
        for(int i = 1 ; i <= N; i++)
            cout<< dame[i] <<" ";
        cout<<endl;
    }
}