#include <cstdio>

using namespace std;
int N;
int col[15],diagp[35],diags[35];
int gata,v[15],nrsol;

void read()
{
    scanf("%d",&N);
}

void back(int k)
{
    for(v[k] = 1 ; v[k] <= N; ++v[k])
        if(k < N)
        {
            if(!col[v[k]] && !diagp[k+v[k]-1] && !diags[N-k+v[k]])
            {
                col[v[k]] = 1;
                diagp[k+v[k]-1] = 1;
                diags[N-k+v[k]] = 1;
                back(k+1);
                col[v[k]] = 0;
                diagp[k+v[k]-1] = 0;
                diags[N-k+v[k]] = 0;
            }
        }
        else
            if(!col[v[k]] && !diagp[k+v[k]-1] && !diags[N-k+v[k]])
            {
                if(!gata)
                {
                    gata = 1;
                    for(int i = 1; i <= N; ++i)printf("%d ",v[i]);
                    printf("\n");
                }
                ++nrsol;
            }
}

int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);

    read();
    back(1);
    printf("%d\n",nrsol);

    return 0;
}