#include <fstream>
#include <algorithm>
#include <cstdio>
using namespace std;



int st[20],n, viz[20];
int nr;

void Afisare()
{
    int i;
    for(i=1;i<=n;i++)
       printf("%d",st[i]);
}
inline int Valid(int top, int x)
{
    int i;
    if (viz[x] == 1) return 0;
    for(i = 1; i < top; i++)
        if(abs(st[i] - x)==abs(top-i)) return 0;
    return 1;
}

inline void Back(int top)
{
    if(top > n)
    {
        if(!nr) Afisare();
        nr++;
        return;
    }
    for(int i = 1; i <= n; i++)
        if (Valid(top,i))
        {
            st[top] = i;
            viz[i] = 1;
            Back(top+1);
            viz[i] = 0;
        }
}

int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    Back(1);
    printf("\n%d",nr);


    return 0;
}