#include <iostream>
#include <fstream>

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

int n, i, j, nr, k, bk[15], rez[15];
bool v[38][38];

void dame () {
    
    if (k == 0)
        for (i = 1; i <= n; i++)
            cout << bk[i] << " ";
    k = 1;
    nr++;
}

void back (int p)
{
    int x = 0;
    for (i = 1; i < p; i++)
    {
        x = p - i;
        v[p][bk[i]] = 1;
        v[p][bk[i]+x] = 1;
        if (bk[i]-x >= 0)   v[p][bk[i]-x] = 1;
    }
    
    for (int i = 1; i <= n; i++)
    {
        if (v[p][i] == 0)
        {
            bk[p] = i;
            if (p == n)     dame();
            else back (p+1);
        }
        v[p][i] = 0;
    }
}

int main () {
    
    cin >> n;
    back(1);
    cout << "\n" << nr;
}