#include <bits/stdc++.h>
using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
int n,nr,s[14],sol[14],k=1;
bool ok,first=1;
bool check()
{
    for(int i=1;i<k;++i)
        if((s[k]==s[i])||((k-i) == abs(s[k]-s[i])))
            return false;
    return true;
}
void solutie()
{
    for(int i=1;i<=n;++i)
        sol[i]=s[i];
}
int main()
{
    in>>n;
    while(k)
    {
        ok=0;
        while(s[k]<n && !ok)
        {
            ++s[k];
            ok=check();
        }
        if(!ok)
            --k;
        else
        {
            if(k==n)
            {
                if(first)
                {
                    solutie();
                    first=0;
                }
                nr++;
            }
            else
            {
                k++;
                s[k]=0;
            }
        }
    }
    for(int i=1;i<=n;++i)
        out<<sol[i]<<' ';
    out<<'\n'<<nr;
    return 0;
}