#include <bits/stdc++.h>

using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n,st[101],nivel,nrsol;
int main()
{
    fin>>n;
    nivel=1;
    while(nivel)
    {
        if(st[nivel]<n)
        {
            st[nivel]++;
            bool ok=1;
            for(int i=1;i<nivel&&ok;i++)
                if(st[nivel]==st[i]||nivel-i==abs(st[nivel]-st[i]))
                    ok=0;
            if(ok)
            {
                if(nivel==n)
                {
                    nrsol++;
                    if(nrsol==1)
                        for(int i=1;i<=n;i++)
                            fout<<st[i]<<" ";
                }
                if(nivel<n)
                {
                    nivel++;
                    st[nivel]=0;
                }
            }
        }
        else
        {
            st[nivel]=0;
            nivel--;
        }
    }
    fout<<'\n'<<nrsol;
    return 0;
}