#include <fstream>
#include <cmath>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
float st[16], n, ok, cnt;
void afis()
{
    if ( ok == 0 )
    {
        for ( int i=1; i<=n; i++)
            g<<st[i]<<" ";

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

    return 1;
}

void back( int k )
{
    for ( int i=1; i<=n; i++)
    {
        st[k] = i;

        if ( control(k) )
            if ( k == n )
            {
                afis();
                ok = 1;
                cnt++;
            }
            else
                back ( k + 1 );
    }
}

int main()
{
    f >> n;
    back(1);
    g<<cnt;
    return 0;
}