#include<fstream>
std::ifstream fin("damesah.in");
std::ofstream fout("damesah.out");
int sol[15], cnt;
int n;
bool found=false, f[20], ds[55], dp[55];
void display()
{
    for(int i=1; i<=n; ++i)
        fout<<sol[i]<<' ';
    fout<<'\n';
}
void back(int k)
{
    if(k==n+1)
    {
        if(!found)
        {
            display();
            found=true;
        }
        ++cnt;
        return;
    }
    for(int j=1; j<=n; ++j)
        if(!f[j] && !dp[k-j+n] && !ds[k+j])
        {
            f[j]=true;
            dp[k-j+n]=true;
            ds[k+j]=true;
            sol[k]=j;
            back(k+1);
            f[j]=false;
            dp[k-j+n]=false;
            ds[k+j]=false;
        }
}
int main()
{
    fin>>n;
    back(1);
    fout<<cnt<<'\n';
    return 0;
}