#include <fstream>
#include <cmath>

using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");

int x[13], sol[13];

void copie (int b[], int a[], int n)
{
    int i;
    for (i = 1; i <= n; i++)
        b[i] = a[i];
}

bool EsteSol(int k)
{
    int i;
    for (i = 1; i < k; i++)
        if (x[k] == x[k] || k - i == abs(x[k] - x[i]))
            return false;
    return true;
}

int generare(int n)
{
    int nrsol = 0, k = 1;
    bool valid = false, confirmat = 0;
    while (k > 0)
    {
        valid = false;
        while((x[k] < n) && (valid == 0))
        {
            x[k]++;
            valid = EsteSol(k);
        }

        if (!valid)
            k--;
        else
        {
            if (k == n)
            {
                if (!confirmat)
                {
                    copie(sol, x, n);
                    confirmat = true;
                }
                nrsol++;
            }
            else
                x[k++] = 0;
        }
    }

    return nrsol;
}

int main()
{
    int xxxx, N, i;
    f >> xxxx;
    N = generare(xxxx);
    for (i = 1; i <= xxxx; i++)
        g << sol[i] << " ";
    g << "\n" << N;
    return 0;
}