#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n, nr = 1, nrsol, k, x[20], c[20], dp[40], ds[40];

inline void afis()
{
    if (nr)
    {
        for (int i=1; i<=n; i++) fout << x[i] << ' ';
        nr = 0;
    }
}

inline int cont (int k)
{
    if (c[x[k]]) return 0;
    if (dp[n + k - x[k]]) return 0;
    if (ds[k + x[k]]) return 0;
    return 1;
}


inline int backtrack(int k)
{
    for (int i=1; i<=n; i++)
    {
        x[k] = i;
        if (cont (k))
        {
            c[x[k]] = dp[n + k - x[k]] = ds[k + x[k]] = 1;
            if (k == n) afis(), nrsol++;
            else backtrack(k + 1);
            c[x[k]] = dp[n + k - x[k]] = ds[k + x[k]] = 0;
        }
    }
}

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