#include <bits/stdc++.h>

using namespace std;
int n,i,k,x[26],j,nr;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
void tipar();
int valid(int k);
void back();
int sol(int k);
int main()
{
    fin>>n;
    back();
    if(nr)
        fout<<"\n"<<nr;
    return 0;
}
void tipar()
{
    nr++;
    if(nr==1)
        for(i=1; i<=k; i++)
            fout<<x[i]<<" ";
  /*  for(i=1; i<=k; i++)
    {
        for(j=1; j<=k; j++)
            if(x[i]==j)
                cout<<setw(4)<<"R";
            else
                cout<<setw(4)<<"#";
        cout<<endl;
    }
    cout<<endl;*/
}
int valid(int k)
{
    ///elementul X[i] stocheaza indicele coloanei pe care se afla regina i
    for(i=1; i<k; i++)
    {
        if(x[k]==x[i])
            return 0;
        if(k-i==abs(x[k]-x[i]))
            return 0;
    }
    return 1;
}
int sol(int k)
{
    return (k==n);
}
void back()
{
    bool ok=0;
    k=1;
    x[k]=0;
    while(k)
    {
        ok=0;
        while(x[k] < n  && !ok)
        {
            x[k]++;
            if(valid(k))
                ok=1;
        }
        if(ok)
            if(sol(k))
                // if(x[k]==1)
                tipar();
        // else ;
            else
                x[++k]=0;
        else
            k--;
    }
}