#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];

vector <int> fSol;

void Push_Sol()
{
    nrSol++;

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

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)
{
    if(p == N + 1)
        {
            Push_Sol();
            return ;
        }

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

                d[i] = 1;

                if(Check_Diagonals(p))
                    bk(p + 1);

                d[i] = 0;
            }
}

int main()
{
    fin >> N;

    bk(1);

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

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

    return 0;
}