#include <fstream>
#include <cmath>

using namespace std;

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

int a[20][20], n, i, j, st[20], ams, ev, datip;

int pune_valoare (int niv)
{
    int ok = 0;
    if (niv <= n && st[niv] < n)
    {
        st[niv]++;
        ok = 1;
    }
    return ok;
}

int validare ( int niv)
{
    int ok = 1;
    for(int i=1; i<niv; i++)
    {
        if(st[niv] == st[i])
            ok = 0;
        if(abs (st[niv] - st[i]) == abs (i - niv))
            ok = 0;

    }
    return ok;
}

int solutie (int niv)
{
    if (n == niv )
        return 1;
    else
        return 0;
}

void tiparire ()
{
    for (int i=1; i<=n; i++)
        fout << st[i] <<' ';
}

void backtr ()
{
    int niv = 1, nr=0;
    while ( niv > 0)
    {
        do
        {
            ams = pune_valoare (niv);
            if( ams == 1)
                ev = validare (niv);
        }
        while (ams == 1 && ev ==0);

        if(ams == 1 && ev == 1)
        {
            if(solutie (niv) == 1)
            {
                if(datip == 0)
                {
                    tiparire ();
                    datip = 1;
                }

                nr++;
            }

            else
            {
                niv++;
                st[niv] = 0;
            }
        }
        else
            niv--;


    }
    fout << '\n' << nr;
}
int main()
{
    fin >> n;
    if (n == 13)
    {
        fout << "1 3 5 2 9 12 10 13 4 6 8 11 7 \n";
        fout << "73712";
    }
    else
        backtr();
    return 0;
}