#include<iostream>
#include<cstring>
#include<fstream>
#include<algorithm>
#include<vector>
#include<bitset>
#include<iomanip>
using namespace std;
fstream fin("damesah.in",ios::in),fout("damesah.out",ios::out);
int n,p=0,drum[15];
bool coloana[15],diag1[30],diag2[30];
void scrie(int k)
{
    int i;
    for(i=1;i<k;i++)
    {
        cout<<drum[i]<<" ";
    }
    cout<<"\n";
    return ;
}
void back(int k)
{
    int i;
    if(k==n+1)
    {
        if(p==0)
        {
            for(i=1;i<=n;i++)
            {
                fout<<drum[i]<<" ";
            }
            fout<<"\n";
        }
        p++;
    }
    else
    {
        for(i=1;i<=n;i++)
        {
            if(coloana[i]==0 && diag1[n-k+i]==0 && diag2[k+i-1]==0)
            {
                drum[k]=i;
                diag1[n-k+i]=diag2[k+i-1]=coloana[i]=true;
                back(k+1);
                diag1[n-k+i]=diag2[k+i-1]=coloana[i]=false;
            }
        }
    }
}
int main()
{
    fin>>n;
    back(1);
    fout<<p<<"\n";
    cout<<p<<"\n";
    fout.close();
    fin.close();
    return 0;
}