#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];

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

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

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 (Valid(k))
                if (k == n)
                    {
                     ++nrsol;
                     if (nrsol == 1) Afisare(k);
                    }
                else Back(k+1);
         viz[i] = false;
        }
}

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