#include <cstdio>
#define NMax 14

using namespace std;

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)
        printf("%d ", x[i]);
    printf("\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()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    Back(1);
    printf("%lld", nrsol);
    return 0;
}