#include <fstream>
#define NMax 14

using namespace std;

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

int x[NMax], n;
long long nrsol;
bool viz[NMax], l[NMax * 2], c[NMax*2];

inline int abs(int x)
{
    if (x < 0) return -x;
    else return x;
}

void Afisare(int n)
{
    int i;
    for (i = 1; i <= n; ++i)
        fout << x[i] << " ";
    fout << "\n";
}

void Back(int k)
{
    int i;
    for (i = 1; i <= n; ++i)
        if (!viz[i])
            {
             x[k] = i;
             viz[i] = true;
             if (!l[i - k + n - 1] && !c[k + i])
                if (k == n)
                    {
                     ++nrsol;
                     if (nrsol == 1) Afisare(k);
                    }
                else
                    {
                     l[i - k + n - 1] = c[k + i] = true;
                     Back(k+1);
                     l[i - k + n - 1] = c[k + i] = false;
                    }
         viz[i] = false;
        }
}

int main()
{
    fin >> n;
    fin.close();
    Back(1);
    fout << nrsol << "\n";
    fout.close();
    return 0;
}