#include <fstream>

#define MAX_N 15

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int regine[MAX_N];
bool col[MAX_N], diagP[MAX_N*2], diagS[MAX_N*2];
int ans, n;

void bkt(int l);

int main()
{
    fin >> n;
    
    bkt(0);
    fout << ans << "\n";

    return 0;
}

void bkt(int l)
{
    if (l==n)
    {
        if (ans < 1)
        {
            for (int c=0; c<n; c++)
                fout << regine[c]+1 << " ";
            fout << "\n";
        }
        ++ans;
    }
    else 
    {
        for (int c=0; c<n; c++)
        {
            if (!col[c] && !diagP[c-l+n-1] && !diagS[l+c])
            {
                regine[l] = c;
                col[c] = diagP[c-l+n-1] = diagS[l+c] = true;
                bkt(l+1);
                col[c] = diagP[c-l+n-1] = diagS[l+c] = false;
            }
        }
    }
}