#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 13;

int N;

int st[NMAX + 5], nrSol;
bool d[NMAX + 5];

bool foundSol = false;
vector <int> fSol;

void Push_Sol()
{
    if(!foundSol)
    {
        foundSol = true;

        for(int i = 1; i <= N; i++)
            fSol.push_back(st[i]);
    }

    nrSol++;
}

int ABS(int x)
{
    return max(x, -x);
}

bool Check_Diagonals(int p)
{
    for(int i = 1; i < p; i++)
        if(ABS(p - i) == ABS(st[p] - st[i]))
            return false;

    return true;
}

void bk(int p)
{
    for(int i = 1; i <= N; i++)
        if(!d[i])
        {
            st[p] = i;

            d[i] = 1;

            if(Check_Diagonals(p))
                if(p != N)
                    bk(p + 1);
                else
                    Push_Sol();

            d[i] = 0;
        }
}

int main()
{
    fin >> N;

    bk(1);

    for(auto it : fSol)
        fout << it << ' ';

    fout << '\n' << nrSol << '\n';

    return 0;
}