#include <iostream>
#include <stdlib.h>
#include <fstream>
#define ma 100
using namespace std;
int a[ma],n,k,c=0;
ifstream f("damesah.in");
ofstream g("damesah.out");
void scriere()
{int i;
for (i=1;i<=n;i++) g<<a[i];
g<<'\n';}
int ok(int k,int j)
{int i,v=1;
for (i=1;i<k;i++)
{if ((j==a[i])||((k-i)==abs(j-a[i]))) v=0;}
if (v==1) return 1;
}
void bkt (int k)
{int i;
for (i=1;i<=n;i++)
{if (ok(k,i)==1) {if (k<n) {a[k]=i;
                           bkt(k+1);}
                 if(k==n)  {a[k]=i;
                            c=c+1;
                            if (c==1) scriere();}}
}
}

int main()
{
f>>n;
bkt(1);
g<<c;
f.close();
g.close();
return 0;
}