#include <fstream>
using namespace std;
ifstream fin ("damesah.in");
ofstream fout ("damesah.out");
#define NMAX 20

int v[NMAX], n, total, sol[NMAX];
bool u[NMAX], dp[NMAX * 2], ds[NMAX * 2];

int modul(int a) {
    if(a < 0)
        return (-1) * a;
    return a;
}

void Back(int k) {
    int i;
    for(i=1; i<=n; i++) {
        if(!u[i] && !dp[i + k -1] && !ds[k - i + n]) {
                u[i] = true;
                dp[i + k -1] = true;
                ds[k - i + n] = true;
                v[k] = i;

                if(k == n) {
                    if(!total)
                        for(int j=1; j<=n; j++)
                            sol[j] = v[j];

                    total++;
                } else Back(k + 1);

                u[i] = false;
                dp[i + k -1] = false;
                ds[k - i + n] = false;
        }
    }
}

int main()
{
    fin >> n;

    Back(1);

    if(total) {
        for(int i=1; i<=n; i++)
            fout << sol[i] << " ";
        fout << endl << total;
    }

    return 0;
}