#include <fstream>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int n, sol[15],prima, nr;
int col[15], dp[30], ds[30];

void Afisare()
{
    for(int i = 1; i <= n; i++)
        fout << sol[i] << " ";
    fout << "\n";
}

void Back(int k)
{
    int i;
    for(i = 1; i <= n; i++)
    {
        if(col[i]==0 && dp[n-(k-i)]==0 && ds[k+i-1]==0)
        {
            sol[k]=i;
            col[i]=1;
            dp[n-(k-i)]=1;
            ds[k+i-1]=1;
                if(k == n)
                {
                    nr++;
                    if(prima==0)
                    {
                        Afisare();
                        prima = 1;
                    }
                }
                Back(k+1);
                col[i]=0;
                dp[n-(k-i)]=0;
                ds[k+i-1]=0;

        }
    }

}


int main()
{
    fin>>n;
    Back(1);
    fout << nr;
    return 0;
}