#include <fstream>

using namespace std;

int m,cnt;

ifstream f("damesah.in");
ofstream g("damesah.out");

int c[30],d1[30],d2[30],v[30];

void bk(int n)
{
    int i;
    if(n==m+1)
    {
        if(!cnt)
        {
            for(i=1; i<= m; i++)
                if(v[i])
                    g<<v[i]<<" ";
                    g<<'\n';
                    cnt++;
        }
        else cnt++;
    }
    for(i=1; i<=m; i++)
        if(c[i] == 0 && d1[i+n] == 0 && d2[i-n+m+1] == 0)
            {
                v[n]=i;
                c[i] = 1;
                d1[i+n] = 1;
                d2[i-n+m+1] = 1;
                bk(n+1);
                c[i] = 0;
                d1[i+n] = 0;
                d2[i-n+m+1] = 0;
            }
}
int main()
{
    f>>m;
    bk(1);
    g<<cnt;
    return 0;
}