#include <fstream>
#include <cstdlib>
using namespace std;

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

int n;
int x[14];
int nrsol = 0;

bool valid(int k)
{
    for (int i = 1; i < k; i++)
    {
        // aceeasi coloana
        if (x[i] == x[k])
            return false;

        // aceeasi diagonala
        if (abs(x[i] - x[k]) == abs(i - k))
            return false;
    }

    return true;
}

void back(int k)
{
    for (int c = 1; c <= n; c++)
    {
        x[k] = c;

        if (valid(k))
        {
            if (k == n)
            {
                nrsol++;

                // Prima solutie gasita este cea lexicografic minima
                if (nrsol == 1)
                {
                    for (int i = 1; i <= n; i++)
                    {
                        fout << x[i];

                        if (i < n)
                            fout << " ";
                    }

                    fout << '\n';
                }
            }
            else
            {
                back(k + 1);
            }
        }
    }
}

int main()
{
    fin >> n;

    back(1);

    fout << nrsol << '\n';

    fin.close();
    fout.close();

    return 0;
}