#include <fstream>

using namespace std;

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

int sol[14],wh[14],n,cnt;
bool line[14],diag1[30],diag2[30],ok;

void back (int i)
{
    if (i==n+1)
    {
        if (!ok)
        {
            ok = 1;
            for (int i=1; i<=n; ++i)
            {
                sol[i] = wh[i];
            }
        }
        ++cnt;
    }

    for (int j=1; j<=n; ++j)
    {
        if (!line[j] && !diag1[i-j+n] && !diag2[i+j])
        {
            line[j] = 1;
            diag1[i-j+n] = 1;
            diag2[i+j] = 1;
            wh[i] = j;

            back (i+1);

            line[j] = 0;
            diag1[i-j+n] = 0;
            diag2[i+j] = 0;
        }
    }
}

int main()
{
    fin>>n;

    back (1);

    for (int i=1; i<=n; ++i)
    {
        fout<<sol[i]<<" ";
    }
    fout<<"\n"<<cnt;
}