#include <fstream>
#include <deque>

using File = std::fstream;

File in, out;

int sol, st[20], n, k, as, ev;

void init(int st[], int k)
{
    st[k]=0;
}

int succesor(int st[], int k)
{
    if(st[k]<n)
    {
        st[k]++;
        return 1;
    }
    else return 0;
}

int valid(int st[], int k)
{
    int i;
    for(i=1; i<=k-1; i++)
    {
        if(st[k]==st[i] ||
           abs(st[k]-st[i])==k-i) return 0;
    }

    return 1;
}

int solutie(int k)
{
    return (k==n);
}

void tipar(int k)
{
    sol++;
}

void bkt()
{
    k=1;
    init(st, k);
    while(k)
    {
        as=1;
        ev=0;
        while(as && !ev)
        {
            as=succesor(st, k);
            if(as) ev=valid(st, k);
        }

        if(as)
        {
            if(solutie(k))
            {
                sol++;
                if(sol==1) for(int i=1; i<=n; i++) out<<st[i]<<' ';
            }
            else
            {
                k++;
                init(st, k);
            }
        }
        else k--;
    }
}

int main()
{
	in.open("damesah.in", File::in);
	out.open("damesah.out", File::out | File::trunc);

    in>>n;

    bkt();

    out<<'\n'<<sol;

    return 0;
}