#include <bits/stdc++.h>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

const int mm=14;
int sol,n,v[mm],ap[mm];

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;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 backt()
{
    bool as,ev;
    int k=1,st[mm];
    init(st,k);
    while(k>0)
    {
        as=1;
        ev=0;
        while(as && !ev)
        {
            as=succesor(st,k);
            if(as)
                ev=valid(st,k);
        }
        if(as)
            if(solutie(k))
            {
                tipar(k);
                if(sol==1)
                    for(int i=1;i<=n;i++)
                        fout << st[i] << " ";
            }
            else
            {
                k++;
                init(st,k);
            }
        else
            k--;
    }
}

int main()
{
    fin >> n;
    backt();
    fout << '\n' << sol;
    return 0;
}