#include <fstream>
#include <cmath>

using namespace std;

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

struct solutie
{
    int x;
    int sol;
}v[13];
void afisareSolutie(int n)
{
    for(int i=1;i<=n;i++)
        v[i].sol=v[i].x;
}
bool valid(int k)
{
    for(int i=1;i<k;i++)
        if((v[k].x==v[i].x) || (k-i==abs(v[k].x-v[i].x)))
           return false;
    return true;
}
int backtrack(int n)
{
    bool eSolutie;
    int k=1;
    v[k].x=0;
    int nrsol=0;
    bool prima=1;
    while(k>0)
    {
        eSolutie=0;
        while(v[k].x<n && (!eSolutie))
        {
            v[k].x++;
            eSolutie=valid(k);
        }
        if(!eSolutie)
            k--;
        else
        {
            if(k==n)
            {
                if(prima)
                {
                    afisareSolutie(n);
                    prima=0;
                }
                nrsol++;
            }
            else
                v[++k].x=0;
        }
    }
    return nrsol;
}
int n,k,nrsol;
int main()
{
    fin>>n;
    nrsol=backtrack(n);
    for(int i=1;i<=n;i++)
        fout<<v[i].sol<<" ";
    fout<<'\n'<<nrsol;
    return 0;
}