#include <fstream>

using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");
int n;
int col[50], mdig[50], sdig[50];
int ans = 0;
int dame[50];

void bk(int l)
{
    if(l == n)
    {
        if(ans < 1)
        {
            for(int i = 0; i<n; i++)
            {
                g<<dame[i]+1<<" ";
            }
            g<<'\n';
        }
        ans++;
    }
    else
    {
        for(int c = 0; c<n; c++)
        {
            if(col[c] == 0 && mdig[c-l+n-1] == 0 && sdig[l+c] == 0)
            {
                dame[l] = c;

                col[c] = mdig[c-l+n-1] = sdig[l+c] = 1;
                bk(l+1);
                col[c] = mdig[c-l+n-1] = sdig[l+c] = 0;
            }
        }
    }
}

int main()
{
    f>>n;
    bk(0);
    g<<ans;
    return 0;
}