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

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

inline int cont (int k)
{
    int dig;
    for (int i=1; i<=k-1; i++)
    {
        if (x[i] == x[k]) return 0;
        if (x[k] - x[i] < 0) dig = x[i] - x[k];
        else                 dig = x[k] - x[i];
        if (dig == k - i) return 0;
    }
    return 1;
}


inline int backtrack(int n)
{
    int k = 1;
    do
    {
        while (x[k] < n)
        {
            x[k]++;
            if (cont(k))
            {
                if (k == n) afis(), nrsol++;
                else x[++k] = 0;
            }
        }
        k--;
    }
    while (k);
}

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