#include<fstream>
using namespace std;
ifstream f("damesah.in",ios::in);
ofstream g("damesah.out",ios::out);
int x[20],s[20];
void scriere( int n)
{
     int i;
     for(i=1;i<=n;i++)
     s[i]=x[i];}
int valid( int k )
{
    int i;
    for(i=1;i<k;i++)
    if(x[i]==x[k] || abs(x[i]-x[k])==abs(i-k) ) 
    return 0;
    return 1;}
int back( int n)
{
    int sol,k,nrsol=0,prima=1;
    k=1;
    x[k]=0;
    while(k>0)
    {
              sol=0;
              while( (x[k]<n) && (sol==0) )
              {
                     x[k]++;
                     sol=valid(k);}
              if(sol==0)
              k--;
              else
              {
                  if(k==n)
                  { if(prima){
                          scriere(n);
                          prima=0;}
                  nrsol++;}
              else
              {k++;
              x[k]=0;}}}
    return nrsol;}
int main()
{
    int n,k,nrsol,i;
    f>>n;
    nrsol=back(n);
    for(i=1;i<=n;i++)
    g<<s[i]<<' ';
    g<<'\n';
    g<<nrsol;
    return 0;}