#include <iostream>
#include <fstream>

using namespace std;

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

struct dame{
    int y, d1, d2;
}v[100];
int n, s = 0;

void afisare()
{
    for(int i = 1; i <= n; ++i)
        g << v[i].y << " ";
}

bool solutie(int k)
{
    return k == n;
}

bool ok(int k)
{
    for(int i = 1; i < k; i++)
        if((v[i].d1 == v[k].d1) || (v[i].d2 == v[k].d2) || (v[i].y == v[k].y))
        return false;
    return true;
}

void btk(int k)
{
    for(int i = 1; i <= n; i++)
    {
        v[k].y = i;
        v[k].d1 = k + v[k].y - 1;
        v[k].d2 = n - v[k].y + k;

        if(ok(k))
        {
            if(solutie(k))
            {
                if(s == 0)
                    {
                        afisare();
                        s++;
                    }
                else
                    s++;
            }
            else
                btk(k + 1);
        }
    }
}
int main()
{
    f >> n;

    btk(1);

    g << "\n" << s;

    f.close();
    g.close();

    return 0;
}